哈林圖Wiener指標的若干極值問題

劉順琴

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

哈林圖Wiener指標的若干極值問題

劉順琴

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

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

哈林圖；Wiener指標；最大；最小

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

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

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

一、Wiener數最小的哈林圖

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

進一步地，當H是一個哈林圖時，不難看出上述等號成立當且僅當H是輪圖L(n)．定理證畢．

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

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

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

二、直徑為3的樹對應的哈林極圖

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

顯然距離為1的點對的數目nd1即該圖的邊數m，所以

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

距離為2的點對的數目由以下5個部分組成：

1.{u}和{v1,v2,……vt}, 其中u和{v1,v2,……vt}中的任何頂點距離均為2, 點對的數目為t；

2.{v}和{u1,u2,……us}，其中v和{u1,u2,……us}中的任何頂點的距離均為2, 點對的數目為s；

當樹圖的直徑大于等于4時，在其對應的哈林圖中，我們認為Wiener數最大和最小的哈林圖并不唯一，下面我們分別給出了頂點數為10，直徑為4的樹圖對應的哈林圖，Wiener數最大兩個圖 和 ，Wiener數最小的兩個圖 和 :

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

三、不等式設T是滿足分支點度數大于等于3的樹，T有t片樹葉，H是T對應的哈林圖，則T和H的Wiener數之間存在著如下關系。

定理3: 設T是滿足分支點度數大于等于3的樹，T有t片樹葉，H是T對應的哈林圖，則W(H)≤W(T)-t.其中W(H)=W(T)-t當且僅當T是星圖，而自然H是輪圖。

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

[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

［責任編輯：劉麗杰］

2014-03-12

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