李丹怡，陳烏險(xiǎn)，晏衛(wèi)根

（集美大學(xué)理學(xué)院，福建 廈門(mén)361021）

0 引言

設(shè)G＝（V，E）是一個(gè)連通的簡(jiǎn)單圖，其中，V是頂點(diǎn)集，E是邊集。連通圖G的Wiener 指標(biāo)［1］定義為

其中，dG（u，v）表示G中頂點(diǎn)u和v之間的距離。

在圖論中，把一個(gè)化學(xué)分子的原子用頂點(diǎn)表示，原子間形成的化學(xué)鍵用邊表示，這樣得到的圖稱(chēng)為此化學(xué)分子對(duì)應(yīng)的分子圖［2-3］。分子圖的圖論不變量可以預(yù)測(cè)相應(yīng)分子的物理與化學(xué)性質(zhì)，這種不變量稱(chēng)為分子圖的拓?fù)渲笜?biāo)。早在1947 年，Wiener 為了研究無(wú)圈分子圖的化學(xué)性質(zhì)就提出了圖的Wiener 指標(biāo)的概念［1］，而式（1）則由文獻(xiàn)［4］首次提出，以此來(lái)預(yù)測(cè)鏈烷烴的沸點(diǎn)［1］。文獻(xiàn)［4］還發(fā)現(xiàn)，Wiener 指標(biāo)和化合物的化學(xué)性質(zhì)之間有很強(qiáng)的相關(guān)性?？梢哉f(shuō)，Wiener 指標(biāo)是迄今為止組合（數(shù)學(xué)）化學(xué)中最重要的拓?fù)渲笜?biāo)之一，是數(shù)學(xué)化學(xué)領(lǐng)域（特別是圖論）中的一個(gè)熱門(mén)研究問(wèn)題，得到了許多數(shù)學(xué)化學(xué)家與組合學(xué)家的重點(diǎn)關(guān)注［5-7］。

目前，關(guān)于樹(shù)（無(wú)圈分子圖）的Wiener 指標(biāo)已經(jīng)有大量的研究結(jié)果［7-8］。眾所周知，所有n階樹(shù)中，星形樹(shù)Sn和路Pn分別是Wiener 指標(biāo)最小和最大的樹(shù)［9］。文獻(xiàn)［10］確定了所有給定最大度的n 階樹(shù)中Wiener 指標(biāo)最小的樹(shù)。文獻(xiàn)［11］也給出：在所有給定頂點(diǎn)度序列的n階樹(shù)中，貪婪樹(shù)的Wiener 指標(biāo)最小，貪婪毛毛蟲(chóng)樹(shù)的Wiener 指標(biāo)最大。這里的貪婪樹(shù)是由貪婪算法得到的樹(shù)，具體定義參見(jiàn)文獻(xiàn)［11］；貪婪毛毛蟲(chóng)樹(shù)［12］是指具有度序列為（d1，…，dn）（d1≥d2≥…≥dk≥2＞dk＋1＝1）的樹(shù)，它由給長(zhǎng)為k-1 的路v1-v2-…-vk添加懸掛邊，使其度序列為d（v1）≥d（vk）≥d（v2）≥d（vk-1）≥…≥d（v［（k＋1）／2］）而得到。如果一個(gè)樹(shù)刪去其所有懸掛頂點(diǎn)后得到一條路，則稱(chēng)該樹(shù)為毛毛蟲(chóng)樹(shù)。文獻(xiàn)［13］刻畫(huà)了每個(gè)頂點(diǎn)的度都為奇數(shù)的n階樹(shù)中具有最大與最小Wiener 指標(biāo)的樹(shù)。

給定兩個(gè)滿(mǎn)足n-1≥d≥2 的正整數(shù)n和d，設(shè)S1（n，d）是只有一個(gè)頂點(diǎn)u的度是d，而其他頂點(diǎn)v（v≠u(mài)）的度都不超過(guò)2 的n階樹(shù)的集合。因此，由S1（n，d）的定義可以看出，S1（n，d）中的樹(shù)有d條路P1，P2，…，Pd，且它們僅有一個(gè)公共頂點(diǎn)u。分別用n1，n2，…，nd表示這d條路P1，P2，…，Pd的長(zhǎng)度，則有n-1＝。為了方便，下文中記這種樹(shù)為T(mén)（n；n1，n2，…，nd）。很顯然，S1（n，d）＝。文獻(xiàn)［14］研究了S1（n，d）中樹(shù)的Wiener指標(biāo)與相應(yīng)的偏序之間的關(guān)系，并刻畫(huà)了這類(lèi)樹(shù)的Wiener 指標(biāo)的極值。

令Sd＋1表示頂點(diǎn)集為｛v0，v1，…，vd｝、中心為v0的星形樹(shù)。設(shè)n1≥n2≥…≥nd是d個(gè)非負(fù)整數(shù)，在Sd＋1中的每個(gè)頂點(diǎn)vi（i＝1，2，…，d）上添加ni（ni≥0）條懸掛邊，從而得到一個(gè)n階類(lèi)星樹(shù)（n＝＋d＋1），記為S（n；n1，n2，…，nd）。文獻(xiàn)［15］稱(chēng)這類(lèi)樹(shù)為繁星，并解決了繁星的極值能量問(wèn)題。文獻(xiàn)［16］證明了在所有的n階繁星樹(shù)S（n；n1，n2，…，nd）中S（n；n-d-1，0，…，0）的Wiener 指標(biāo)最小，的Wiener 指標(biāo)最大，其中n-d-1＝kd＋r。

對(duì)于兩個(gè)不相交的星形樹(shù)Sr＋1和St＋1，其頂點(diǎn)集分別為｛u0，u1，…，ur｝和｛v0，v1，…，vt｝。本文將用一條邊連接它們的兩個(gè)中心點(diǎn)u0和v0而得到的樹(shù)稱(chēng)為雙星，記為Sr，t（t≥r≥1）。例如，雙星S2，3如圖1 所示。

圖1 雙星S2，3Fig.1 A double star S2，3

給定兩個(gè)非負(fù)整數(shù)n與m，設(shè)X＝（n1，n2，…，nr）和Y＝（m1，m2，…，mt）是兩個(gè)非負(fù)整數(shù)序列，其中n1≥n2≥…≥nr≥0，m1≥m2≥…≥mt≥0，且滿(mǎn)足＝n和＝m。設(shè)DSr，t（n，m；X，Y）表示分別在上述雙星Sr，t的每個(gè)頂點(diǎn)ui（1≤i≤r）上添加ni條懸掛邊，在每個(gè)頂點(diǎn)vj（1≤j≤t）上添加mj條懸掛邊后得到的N階樹(shù)，其中N＝r＋t＋n＋m＋2。令DS（r，t；n，m）＝｛DSr，t（n，m；X，Y）＝m｝。一個(gè)樹(shù)T被稱(chēng)為雙繁星，若存在4 個(gè)滿(mǎn)足t≥r≥1、m＋n≥1 的整數(shù)r，t，n，m，使得T∈DS（r，t；n，m）。對(duì)于2 個(gè)非負(fù)整數(shù)序列X＝（3，1）、Y＝（2，2，1）的雙繁星DS2，3（4，5；X，Y）如圖2 所示。

圖2 雙繁星DS2,3(4,5;X,Y)（X=(3,1)，Y=(2,2,1)）Fig.2 A blossomed double star DS2,3(4,5;X,Y)for X=(3,1)and Y=(2,2,1)

本文考慮DS（r，t；n，m）中雙繁星Wiener 指標(biāo)的極值問(wèn)題，刻畫(huà)了具有最小Wiener 指數(shù)的雙繁星。

1 主要結(jié)果及其證明

首先介紹一個(gè)關(guān)于Wiener 指標(biāo)方面的重要結(jié)果。

引理1［1］設(shè)T是一個(gè)邊集為E的樹(shù)，則T的Wiener 指標(biāo)

其中：求和中e跑遍T(mén)的所有邊；nx（e）表示T-e中包含頂點(diǎn)x那個(gè)分支的頂點(diǎn)數(shù)，T-e是從T中刪去邊e所得的子圖。

本文還需要證明以下引理2 和引理3，它們將在后面主要結(jié)果的證明中起關(guān)鍵作用。

引理2設(shè)DSr，t（n，m；X，Y）是一個(gè)N＝r＋t＋2＋n＋m階雙繁星，其中X＝（n1，n2，…，nr），Y＝（m1，m2，…，mt）。對(duì)于給定的正整數(shù)i與j（1≤i＜j≤r），如果有ni-nj≥2，設(shè)X′＝（n1，…，ni-1，…，nj＋1，…，nr），那么

相似地，對(duì)于給定的正整數(shù)k，l（1≤k＜l≤t），如果mk-ml≥2，可以令Y′＝（m1，…，mk-1，…，ml＋1，…，mt），那么

證明設(shè)T＝DSr，t（n，m；X，Y），T′＝DSr，t（n，m；X′，Y）。對(duì)T與T′，利用引理1，不難得到：W（T）-W（T′）＝（ni＋1）（N-ni-1）＋（nj＋1）（N-nj-1）-ni（N-ni）-（nj＋2）（N-nj-2）＝-2（ni-nj-1）。因?yàn)閚i-nj≥2，因此W（T）-W（T′）＜0。

同理可以證明式（4）的不等式成立。故引理2 得證。

引理3設(shè)DSr，t（n，m；X，Y）是一個(gè)N＝r＋t＋2＋n＋m階雙繁星，其中X＝（n，0，…，0），Y＝（m，0，…，0）。如果n≥1，m-n≥（r-t-3）／3，令X′＝（n-1，0，…，0），Y′＝（m＋1，0，…，0），那么W（DSr，t（n，m；X，Y））≥W（DSr，t（n-1，m＋1；X′，Y′）），當(dāng)且僅當(dāng)m-n＝（r-t-3）／3 時(shí)等號(hào)成立。

證明設(shè)T＝DSr，t（n，m；X，Y），T′＝DSr，t（n-1，m＋1；X′，Y′）。由引理1 可知：W（T）-W（T′）＝（n＋1）（N-n-1）＋（n＋r＋1）（m＋t＋1）＋（m＋1）（N-m-1）-n（N-n）-（n＋r）（m＋t＋2）-（m＋2）（N-m-2）＝N-n-n-1-（n＋r）＋t＋m＋1＋m＋1-（N-m-2）＝3m-3n＋t-r＋3。顯然，若m-n＞（r-t-3）／3，有W（T）-W（T′）＞0；若m-n＝（r-t-3）／3，有W（T）＝W（T′）。引理3 證畢。

下面證明本文的3 個(gè)主要結(jié)論定理1～定理3。

定理1對(duì)于4 個(gè)固定的非負(fù)整數(shù)r，t（t≥r≥1），n，m（m＋n≥1），在集合DS（r，t；n，m）中，雙繁星DSr，t（n，m；X°，Y°）的Wiener 指標(biāo)最小，其中。

證明假設(shè)當(dāng)X°＝（n1，n2，…，nr）、Y°＝（m1，m2，…，mt）時(shí)，集合DS（r，t；n，m）中雙繁星DSr，t（n，m；X°，Y°）的Wiener 指標(biāo)最小。對(duì)給定的整數(shù)n＝，若對(duì)1≤i＜j≤r，存在ni≥nj≥1，即（ni＋1）-（nj-1）≥2，可以令X′＝（n1，…，ni＋1，…，nj-1，…，nr）。那么，由引理2，可得W（DSr，t（n，m；X′，Y°））＜W（DSr，t（n，m；X°，Y°）），這與假設(shè)矛盾。

同理，給定整數(shù)m＝，對(duì)任意i，j（1≤i＜j≤t），不存在整數(shù)對(duì)mi和mj，使mi≥mj≥1。因此，在給定非負(fù)整數(shù)r，t，n，m的情況下，集合DS（r，t；n，m）中DSr，t（n，m；X°，Y°）的Wiener 指標(biāo)最小，其中。于是定理1 成立。

當(dāng)r，t，n，m都是固定的整數(shù)時(shí)，定理1 刻畫(huà)了DS（r，t；n，m）中具有最小的Wiener 指標(biāo)的雙繁星為DSr，t（n，m；X°，Y°）。

對(duì)3 個(gè)固定的正整數(shù)r，t（t≥r≥1），n＋m，定義DS（r，t；n＋m）為所有滿(mǎn)足條件x＋y＝m＋n的雙繁星集DS（r，t；x，y）的并集，即DS（r，t；n＋m）＝。當(dāng)r，t，n＋m都是固定的整數(shù)時(shí)，下面的定理2 刻畫(huà)了DS（r，t；n＋m）中具有最小的Wiener 指標(biāo)的雙繁星。

定理2對(duì)固定的正整數(shù)r，t（t≥r≥1），n＋m，則DS（r，t；n＋m）＝：∪｛＝n＋m｝中雙繁星DSr，t（0，n＋m；X*，Y*）的Wiener 指標(biāo)最小，其中。

證明給定非負(fù)整數(shù)r，t（t≥r≥1），n＋m，注意到DS（r，t；n＋m）是所有滿(mǎn)足x＋y＝n＋m的集合DS（r，t；x，y）之并。為了討論DS（r，t；n＋m）中具有最小Wiener 指標(biāo)的雙繁星，可以分為以下3個(gè)步驟：

證明給定正整數(shù)r＋t和n＋m，注意到DS（r＋t；n＋m）是所有滿(mǎn)足x1＋x2＝t＋r，1≤x1≤x2的集合DS（x1，x2；n＋m）之并。

綜上，在給定非負(fù)整數(shù)r＋t、n＋m的情況下，集合DS（r＋t；n＋m）中DS1，r＋t-1（0，n＋m；X°，Y°）的Wiener 指標(biāo)最小，其中X°＝（0），Y°＝。

2 結(jié)論

本文考慮了所謂的雙繁星的最小Wiener 指標(biāo)問(wèn)題。此外，確定雙繁星的最大Wiener 指標(biāo)和能量、譜半徑等許多其他拓?fù)渲笜?biāo)的極值問(wèn)題也是一件非常有意義的工作。而且，雙繁星是一類(lèi)直徑為4 或5 的無(wú)圈分子圖，而無(wú)圈分子圖拓?fù)渲笜?biāo)的極值問(wèn)題可以應(yīng)用于理論化學(xué)中所謂的定量結(jié)構(gòu)-性質(zhì)關(guān)系和定量結(jié)構(gòu)-活性關(guān)系的設(shè)計(jì)，因此也具有很好的研究意義。