劉順琴

（福建師范大學(xué)閩南科技學(xué)院 福建泉州 362332）

哈林圖Wiener指標(biāo)的若干極值問題

劉順琴

（福建師范大學(xué)閩南科技學(xué)院 福建泉州 362332）

一個(gè)連通圖G的Wiener數(shù)(或Wiener指標(biāo))定義為G中所有(無序)頂點(diǎn)對(duì)的距離之和，給出了n階哈林圖中Wiener數(shù)的最小值和對(duì)應(yīng)的極圖；以及直徑為3的樹所對(duì)應(yīng)的哈林圖的Wiener數(shù)的最小值和最大值，并確定了相應(yīng)的極圖；最后，給出了哈林圖Wiener數(shù)的一個(gè)不等式。

哈林圖；Wiener指標(biāo)；最大；最小

定義：哈林圖是這樣一類圖，對(duì)于n(n≥4)階的沒有二度頂點(diǎn)的一棵樹的平面嵌入，將其樹葉按順序連成一個(gè)圈，得到的平面圖稱為哈林圖。

另外用 表示所有n階哈林圖的全體； 表示階數(shù)為n(n≥6),直徑為3的且在分支點(diǎn)的度數(shù)均大于等于3的樹圖所對(duì)應(yīng)的哈林圖的全體，如下圖1所示(其中s+t=n-2,s≥t≥2)，并且定義如下的哈林圖-n階輪圖L(n):

顯然，L(n)是星形圖S(n)(樹)對(duì)應(yīng)的哈林圖，以上兩個(gè)是n階的直徑為3的樹對(duì)應(yīng)的兩個(gè)哈林圖(H3(m)、H3(M))。

一、Wiener數(shù)最小的哈林圖

證明：作為n(n≥4)階樹圖，星圖S(n)的葉子的個(gè)數(shù)為(n-1)．除星圖之外，其它n階樹圖的葉子數(shù)均小于n-1．因此，星圖S(n)所對(duì)應(yīng)的哈林圖，即n階輪圖L(n)的總邊數(shù)為2(n-1)，其它樹圖所對(duì)應(yīng)的哈林圖的邊數(shù)均小于2(n-1).另一方面，在任何一個(gè)連通圖G中，除了每條邊所連接的兩個(gè)頂點(diǎn)之間的距離為1之外，其余的頂點(diǎn)對(duì)之間的距離均不小于2，因此

進(jìn)一步地，當(dāng)H是一個(gè)哈林圖時(shí)，不難看出上述等號(hào)成立當(dāng)且僅當(dāng)H是輪圖L(n)．定理證畢．

推論：n階哈林圖H有，W(H)≥(n-1)(n-2).

證明：n階輪圖L(n)中有2(n-1)個(gè)頂點(diǎn)對(duì)之間有邊連接，剩

再由上面的定理1，推論自然成立.

二、直徑為3的樹對(duì)應(yīng)的哈林極圖

{u},{v},{u1,u2,……us},{v1,v2,……vt}, 對(duì)于H, 其直徑小于等于3，故點(diǎn)與點(diǎn)之間的距離只有三種情況：距離為1，為2，為3。分別考慮這三種情況：

顯然距離為1的點(diǎn)對(duì)的數(shù)目nd1即該圖的邊數(shù)m，所以

nd1=m=n-1+(n-2)=2n-3

距離為2的點(diǎn)對(duì)的數(shù)目由以下5個(gè)部分組成：

1.{u}和{v1,v2,……vt}, 其中u和{v1,v2,……vt}中的任何頂點(diǎn)距離均為2, 點(diǎn)對(duì)的數(shù)目為t；

2.{v}和{u1,u2,……us}，其中v和{u1,u2,……us}中的任何頂點(diǎn)的距離均為2, 點(diǎn)對(duì)的數(shù)目為s；

當(dāng)樹圖的直徑大于等于4時(shí)，在其對(duì)應(yīng)的哈林圖中，我們認(rèn)為Wiener數(shù)最大和最小的哈林圖并不唯一，下面我們分別給出了頂點(diǎn)數(shù)為10，直徑為4的樹圖對(duì)應(yīng)的哈林圖，Wiener數(shù)最大兩個(gè)圖 和 ，Wiener數(shù)最小的兩個(gè)圖 和 :

W( H1)=W(H2)=85, W(H3)=W(H4)=83

三、不等式設(shè)T是滿足分支點(diǎn)度數(shù)大于等于3的樹，T有t片樹葉，H是T對(duì)應(yīng)的哈林圖，則T和H的Wiener數(shù)之間存在著如下關(guān)系。

定理3: 設(shè)T是滿足分支點(diǎn)度數(shù)大于等于3的樹，T有t片樹葉，H是T對(duì)應(yīng)的哈林圖，則W(H)≤W(T)-t.其中W(H)=W(T)-t當(dāng)且僅當(dāng)T是星圖，而自然H是輪圖。

證明：由于T有t片樹葉，故不管這t片樹葉按哪種順序連接成一個(gè)圈使得T變成H時(shí)，總是加了t條邊. 當(dāng)兩個(gè)樹葉之間加一條邊時(shí)，原本距離≥2的兩個(gè)樹葉的距離變成了1，故而每加一條邊，距離至少少于1，加t條邊，所以W(H)≤W(T)-t. 要使得等式成立，則要保證每加一條邊時(shí)Wiener數(shù)剛好少1，則要求相鄰的兩個(gè)樹葉之間的距離必須剛好為2，這就說明了相鄰的兩個(gè)樹葉必須連接在同一個(gè)分支點(diǎn)上，也就是說所有的樹葉必須連接在同一個(gè)分支點(diǎn)上，這樣的樹圖就是星圖，對(duì)應(yīng)的哈林圖當(dāng)然是輪圖. 證明完畢.

[1] L. B. Kier, L. H. Hall, The nature of structure-activity relationships and their relation to molecular connectivity, Europ. J. Med. Chem. 12 (1977) 307-312.

[2] X. Li, J. Zheng, A unified approach to the extremal trees for different indices, MATCH Commun. Math. Comput. Chem. 54 (2005) 195-208.

Some extremal problems of Halin graphs of Wiener index

Liu Shun-qin

(Minnan Science and Technology Institute of Fujian Normal University, Quanzhou Fujian,362332, China)

A connected graph G Wiener number (or Wiener) is defined as the G in all (disorder) vertex and distance. The pole figure of minimum values and the corresponding gives Wiener n order Halin graphs number; number and diameter of 3 Wiener corresponding to the tree Halin graphs of minimum and the maximum value, and determine the corresponding extreme graphs; finally, gives an inequality of Halin graphs of Wiener numbers

Harinto; Wiener index; maximum; minimum

O157.5

A

1000-9795（2014）05-0151-01

［責(zé)任編輯：劉麗杰］

2014-03-12

劉順琴（1981-），女，福建人，講師，從事圖論方向的研究。