歐陽庚旭

(上海電機學院 文理教學部，上海 201306)

設圖G=(V,E)是一個簡單無向連通圖，其中V(G)和E(G)分別是圖G的頂點集和邊集.當連通圖G滿足|E(G)|=|V(G)|+1時，稱G是樹，記為T.頂點v的度指的是與v相鄰的頂點的數(shù)目，記為d(v).度為1的頂點稱為懸掛點，與懸掛點相鄰的邊稱為懸掛邊. 頂點u,v之間的距離指的是u與v之間最短路所含邊的數(shù)目，記為d(u,v).圖G中任意兩頂點距離的最大值稱為圖的直徑，記為dG,簡記為d.n階路和星圖分別記為Pn,Sn.文中未給出的定義和記號參見文獻[1].

1 固定直徑的毛蟲樹的Harary指數(shù)的極值圖

圖1 毛蟲樹

假設H1,H2是兩個連通圖，記H1vH2是一個新的圖，且滿足

V(H1vH2)=V(H1)∪V(H2)，

有

E(H1vH2)=E(H1)∪E(H2)，V(H1)∩V(H2)={v}.

引理1[6]假設H是一個連通圖，Tl是一個n階樹，且

V(H)∩V(Tl)={v}，

則

H(HvTl)≤H(HvSl)，

其中：HvSl是由H和星圖Sl的中心在頂點連接v而成的圖，等號成立當且僅當Tl?Sl.

引理3[7]假設圖G是一個非平凡的連通圖，且v∈V(G)，Gk,l記為圖G在頂點v處添加兩條長分別為k和l的路Pk=vv1v2…vk，Pl=vu1u2…ul而得到的圖G，若k≥l≥1，則

H(Gk,l)>H(Gk+1,l-1).

定理1對于任意階數(shù)為n、直徑為d的非毛蟲樹T，則一定存在毛蟲樹

使得

H(T′)>H(T).

證明假設u,v是非毛蟲樹T中距離最大的兩個頂點，則

d(u,v)=d，

d(u)=d(v)=1，

且在頂點u,v之間存在唯一路P,記P=ux1x2…,xd-1v，對于路P中的任意頂點xi，1≤i≤d-1,不妨設在T中與xi相接的樹的階數(shù)為ni+1，在xi處將ni+1階樹替換為Sni+1.由引理1可知，圖的Harary指數(shù)將變大，不斷重復上述過程，直到非毛蟲樹T變成毛蟲樹

有

H(T′)>H(T).

時成立.

證明首先證明主路只有一個頂點的度大于2.反之，則存在ni>0,nj>0,1≤i,j≤d-1.由引理2可知，將vi的ni個懸掛邊往vj上移或者將vj的nj個懸掛邊往vi上移得到新的樹的Harary指數(shù)將變大，不斷重復上述過程，最終可得主路只有一個頂點度大于2的毛蟲樹.

2 似雙星樹的Harary指數(shù)的極值圖

圖2 似雙星樹T(p,d,q)

引理4[8-10]假設T是任意一個n階樹，有

左邊等號當且僅當T?Pn時成立，右邊等號當且僅當T?Sn時成立.

引理5對任意的整數(shù)對(n,d)，其中d≥2,n≥d+1，有

證明根據(jù)圖的Harary指數(shù)的定義和引理4，將樹T(p,d,q)的頂點分成3部分：第一部分頂點{x1}的p個懸掛點、第二部分頂點xd-1的q個懸掛點、第三部分路Pd-1上的d-1個頂點，有

引理6當樹T(p,d,q)的階數(shù)n和直徑d固定時，有

H(T(p,d,q))≤H(T(p-1,d,q+1)).

證明由引理5可得

等號當且僅當d=2，即T(p,d,q)?Sn時成立.

由引理5直接計算可得

引理7當樹T(1,d,n-d)的階數(shù)n固定時，有

H(T(1,d,n-d))≤H(T(1,d-1,n+1-d)).

證明由上面的公式計算得

等號當且僅當d=2，即T(p,d,q)?Sn時成立.

由引理6、定理3和引理7，可得定理4.

定理4T(1,2,n-2)?Sn是樹T(p,d,q)中取得最大Harary指數(shù)的極圖，T(1,n-1,1)?Pn是樹T(p,d,q)中取得最小Harary指數(shù)的極圖.