雙繁星Wiener 指標(biāo)的極值

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

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

0 引言

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

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

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

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

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

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

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

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

給定兩個非負(fù)整數(shù)n與m，設(shè)X＝（n1，n2，…，nr）和Y＝（m1，m2，…，mt）是兩個非負(fù)整數(shù)序列，其中n1≥n2≥…≥nr≥0，m1≥m2≥…≥mt≥0，且滿足＝n和＝m。設(shè)DSr，t（n，m；X，Y）表示分別在上述雙星Sr，t的每個頂點ui（1≤i≤r）上添加ni條懸掛邊，在每個頂點vj（1≤j≤t）上添加mj條懸掛邊后得到的N階樹，其中N＝r＋t＋n＋m＋2。令DS（r，t；n，m）＝｛DSr，t（n，m；X，Y）＝m｝。一個樹T被稱為雙繁星，若存在4 個滿足t≥r≥1、m＋n≥1 的整數(shù)r，t，n，m，使得T∈DS（r，t；n，m）。對于2 個非負(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)的極值問題，刻畫了具有最小Wiener 指數(shù)的雙繁星。

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

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

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

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

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

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

相似地，對于給定的正整數(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）。對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）。因為ni-nj≥2，因此W（T）-W（T′）＜0。

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

引理3設(shè)DSr，t（n，m；X，Y）是一個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è)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 個主要結(jié)論定理1～定理3。

定理1對于4 個固定的非負(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）時，集合DS（r，t；n，m）中雙繁星DSr，t（n，m；X°，Y°）的Wiener 指標(biāo)最小。對給定的整數(shù)n＝，若對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＝，對任意i，j（1≤i＜j≤t），不存在整數(shù)對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ù)時，定理1 刻畫了DS（r，t；n，m）中具有最小的Wiener 指標(biāo)的雙繁星為DSr，t（n，m；X°，Y°）。

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

定理2對固定的正整數(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）是所有滿足x＋y＝n＋m的集合DS（r，t；x，y）之并。為了討論DS（r，t；n＋m）中具有最小Wiener 指標(biāo)的雙繁星，可以分為以下3個步驟：

證明給定正整數(shù)r＋t和n＋m，注意到DS（r＋t；n＋m）是所有滿足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)問題。此外，確定雙繁星的最大Wiener 指標(biāo)和能量、譜半徑等許多其他拓?fù)渲笜?biāo)的極值問題也是一件非常有意義的工作。而且，雙繁星是一類直徑為4 或5 的無圈分子圖，而無圈分子圖拓?fù)渲笜?biāo)的極值問題可以應(yīng)用于理論化學(xué)中所謂的定量結(jié)構(gòu)-性質(zhì)關(guān)系和定量結(jié)構(gòu)-活性關(guān)系的設(shè)計，因此也具有很好的研究意義。