基于圈圖Harary指數減小的圖變換

劉 奇，邵燕靈，胡 鵬

(中北大學 理學院， 太原 030051)

1 背景

設圖G是(簡單)連通圖，V(G),E(G)分別是它的頂點集和邊集，|V(G)|表示圖G的階，dG(v)表示頂點v的度，其中度為1的點稱為懸掛點，與懸掛點相連的邊稱為懸掛邊，dG(u,v)表示頂點u,v之間的距離，即u,v兩點之間的最短路的長度。圖G的圍長指圖G中所有圈的最小圈長。

設圖G是n階連通圖，圖G的Harary指數被定義為：

(1)

如果用γ(G,k) 表示圖G中距離為k的頂點對的數量，則

(2)

用HG(v)表示圖G中頂點v與其他點的距離的倒數之和，稱HG(v)為頂點v的Harary指數，則

(3)

k圈圖是指具有n個頂點和n-1+k條邊的連通圖，用μk(n)表示全體n階k圈圖的集合。用T(n)表示全體n階樹的集合，Pn、Sn、Cn分別表示n階的路、星圖、圈。

本文為了更有效地研究圈圖的Harary指數變化和極值，在基于圈圖的Harary指數減小的方向上，提出了5種有效的圖變換，以三圈圖為例，運用圖變換快捷地推出了它們的Harary指數極小圖，并在一定的觀察基礎上，對k圈圖的Harary指數極小圖作出猜測。

2 引理

引理1[2]設G∈T(n)，n≥2，則圖G的Harary指數滿足

(4)

引理2[9]n階圈Cn的Harary指數為

(5)

設G1,G2分別是m1,m2階連通圖，x∈V(G1)，y∈V(G2)，將頂點x,y合并為一個頂點v得到的m1+m2-1階圖記為G=G1vG2。

引理3[3]設G=G1vG2，則

(6)

設G1,G2,G3分別是m1,m2,m3階連通圖，x∈V(G1)，y1,y2∈V(G2)且y1≠y2，z∈V(G3)，將頂點x,y1合并為一個頂點u，頂點y2,z合并為一個頂點v，得到的m1+m2+m3-2階圖記為G=G1uG2vG3。

引理4 設G=G1uG2vG3，結合引理3，有

引理5[13]設Un,g,k是一個圍長為g的n階單圈圖，圈上某一點連接k條懸掛路，其長度分別為n1,n2,…,nk，記n1≥n2≥…≥nk，若g≤2n1，則

H(Un,g,k)≤H(Un,g+1,k)

(7)

引理6[5]設G∈μ1(n)，則

(8)

3 5種基本圖變換

3.1 變換1：懸掛樹變換

設G是一個圈圖，其中v0是G中某個圈上的點，T是G中以v0為根點的一顆m階懸掛樹。將m階懸掛樹T變成一條以v0為一個端點的m階懸掛路P，得到的圖記為G′，稱G′是由G經過懸掛樹變換得到的圖，見圖1。

圖1 懸掛樹變換

引理7 設G′是由G經過懸掛樹變換得到的圖，則H(G′)

證明設G0是由圖G去掉T的所有邊和除v0之外的所有頂點后剩余的圖，則G=G0v0T，G′=G0v0P。由引理1，H(P)≤H(T)，又顯然

故對任意x∈V(G0)v0，有

從而由引理3可知

<

證明完畢。

3.2 變換2：融懸掛路變換

3.2.1 單圈圖

設G是一個n階單圈圖，C是G中的簡單圈，vi0∈V(C)，i=1,2,…,k，Pli=vi0vi1…vili是G中以vi0為一個端點的li階懸掛路，i=1,2,…,k。將G中的全部懸掛路Pli融合成一條懸掛路，長度為l1+l2+…+lk，記得到的n階圖為G′，稱G′是由G經過融懸掛路變換得到的圖，如圖2所示。

圖2 單圈圖

3.2.2 多圈圖

設G是一個如圖3所示的n階圈圖，其中G1,G3為連通圖，Cm是G中一個長為m的簡單圈，Pli是圈Cm上的li階懸掛路，i=1,2,…,k。G1,G3與Cm至多有兩個交點。將Cm上的全部懸掛路Pli融合成一條懸掛路，長度為l1+l2+…+lk，端點為Cm上一點v0，滿足H(v0)≤H(vi),vi∈V(Cm)。記得到的n階圖為G′，稱G′是由G經過融懸掛路變換得到的圖，如圖3所示。

圖3 一般形式

引理8 設G′是由G經過融懸掛路變換得到的圖，則H(G′)

證明考慮圖2的情形：

記mij=d(vi0vj0)，比較li與mi,i-1,mi,i+1的大小，分兩步移動懸掛路：

第1步mi,i+1≤li(或mi,i-1≤li)，將懸掛路Pli+1(或Pli-1)移至Pli上。

以i=1,m12≤l1為例，圖G1是將圖G中懸掛路Pl2移至Pl1上所得的圖。

dG1(uv2i)-dG(uv2i)=dG1(uv1l1)-dG(uv20)=dG1(uv10)+l1-dG(uv20)=

l1-(dG(uv20)-dG1(uv10))≥l1-(dG(uv10)+dG1(uv20))=l1-m12≥0

類似可證，若mi,i-1≤li，圖G1是將圖G中懸掛路Pli-1移至Pli上所得的圖，則H(G1)≤H(G)。

第2步若尚未得到圖G′，此時mi, i+1≥li且mi, i+1≥li+1。將G中的懸掛路Pl2移至Pl1上，所得圖G2的Harary指數減小，重復可得G′。

設圖G2由圖G1中懸掛路Pl2移至Pl1上所得。

將圖G1上懸掛路Pl2以外的頂點分成3部分：

3)Pl2與其他懸掛路V(Pli),i≥2：

當m2i≤m1i時，顯然有Pl2與Pli之間點對的反距離減小；

當m2i>m1i時，有m1i>m1(i+1)，Pl2與Pli之間點對的反距離增大，

以上3部分結合引理4有

從而H(G2)≤H(G1)。多次重復上述步驟后得到圖G′，即H(G′)≤H(G)。

考慮圖3的情形，根據前面的證明，只需要考慮變換前后懸掛路Pli與G1,G3中點的Harary指數變化。對于懸掛路Pl1，圈Cm上一點v0，滿足H(v0)≤H(vi),vi∈V(Cm)，使得Pl1的端點在v0處時有

(HG′(pl1)-HG2′(pl1))-(HG(pl1)-HG2(pl1))≤0

同理，懸掛路Pl2移動到Pl1的末端點時

(HG′(pl2)-HG2′(pl2))-(HG(pl2)-HG2(pl2))≤0

顯然可以得出

即H(G′)≤H(G)。證畢。

3.3 變換3:圈長變換

設G1，G2，G3為連通圖，G2的階為m，圈長為g(g≥4)，且至多有一條懸掛路，圖G2與G1，G3分別有一個公共點u，v(G1，G3可為空圖)，G=G1uG2vG3。將G2變為由一個3長圈連接一條m-3長懸掛路構成的m階單圈圖G2′，其中點v為G2′的懸掛點，點u為G2′中3長圈的一個2度點，記G′=G1uG2′vG3，稱G′是由G經過圈長變換得到的圖，如圖4所示。

引理9 設G′是由G經過圈長變換得到的圖，則H(G′)≤H(G)。

證明考慮(a)類、(b)類的證明同理。

圖G′=G1uG2′vG3由G=G1uG2vG3經過圈長變換得到。由引理6有

從而H(G2′)-H(G2)<0。由引理4可知

由dG2′(u,v)=m-2>dG2(u,v)，dG2′(u,x)≥dG2(u,x),dG2′(x,v)≥dG2(x,v)(x∈V(G2))，結合引理1和引理2、3知上式中各行的值為負，可得出H(G′)-H(G)<0。證畢。

圖4 圈長變換

3.4 變換4：去合邊變換

3.4.1 雙圈合邊

設G=G1uG2vG3是一個n階圈圖，其中G2是一個m階雙圈圖(如圖5)，圈Cg1與Cg2有k+1個公共點v10,…,v1k(k≥1)，每個圈上至多有一條懸掛路。若k=1，合邊不變，將圈Cg1,Cg2的圈長縮小至g1′=g2′=3，兩圈上其他點形成懸掛路Pl1,Pl2，端點分別在兩圈的非公共頂點上，得到G2′，記G′=G1uG2′vG3，稱G′是由G經過去合邊變換得到的圖。

若k≥2，將圈Cg1,Cg2的圈長縮小至g1′=g2′=3，其余(g1+g2-k-5)個頂點放在兩圈之間構成一條連接兩圈的路，得到G2′，記G′=G1uG2′vG3，稱G′是由G經過去合邊變換得到的圖。

圖5 雙圈合邊

3.4.2 三圈合邊

三圈合邊的情形分為以下4類(見圖6)：

圖6 三圈合邊

引理10 設G′是由G經過去合邊變換得到的圖，則H(G′)≤H(G)。

證明雙圈合邊：

當k=1時，可根據圈長變換證明。

當k≥2時，圖G經過去合邊變換得到圖G′，結合引理3，G2的Harary指數的變化可看做兩部分。

1) 圈Cg1上的點對應圈Cg2上的點對。記圖G中圈Cg1、Cg2經過變換后的部分為，結合引理9中圈長變換的證明可得：

2) 圈Cg1與圈Cg2間的點對。合邊v1v2上的點對變換后的距離沒有變化，合邊以外的點vi、vj(vi∈cg1,vj∈cg2)，有

dG′(vivj)=dG′(viv10)+dG′(v10v1k)+dG′(v1kvj)≥dG(viv10)+dG(v10v1k)+dG(v1kvj)≥dG(vivj)

考慮G1、G3，任取v1∈G1,v2∈G2,v3∈G3，顯然有dG′(vi,vj)≥dG(vi,vj)，結合引理3的證明可得H(G′)-H(G)<0。

三圈合邊：

記圖G中圈C1經過變換后的部分為C1′，對于圖G中圈C1上任一點v，結合引理3，有Hc1′(v)≤Hc1(v)，且

對于圖G中圈C3，同理可得Hc3′(v)≤Hc3(v)，且

考慮弧v1v2上的內點，對于點v5，計算對比后容易得出HG2′(v3)≤HG2(v3)。對于弧v1v2上除v5以外的任一內點v，有HG2′v3(v)≤HG2v3(v)，且

情形4：設G′是由G經過去合邊變換得到。

記圖G中路徑v0v1u1、v0v2u2、v0v3u3為P1、P2、P3，經過變換后的部分為P1′、P2′、P3′。結合引理3，對于P1上u1以外的點v，有H(P1′v)≤H(P1v)且

任取v1∈P1,v2∈P2,v3∈P3，顯然有dG′(vi,vj)≥dG(vi,vj)。對于圖G中路徑P2、P3上u2、u3以外的點v，同理可得H(P2′v)≤H(P2v),H(P3′v)≤H(P3v)，且

考慮點u1、u2、u3有

同理，HG2′(u2)≤HG2(u2),HG2′(u3)≤HG2(u3)。

綜上可以得出H(G2′)≤H(G2)。

此時只需證明HG′(v)≤HG(v)(任意v∈V(G)V(G2))，即可得出H(G′)≤H(G)。任取v∈V(G)V(G2)，顯然有HG2′(v)≤HG2(v)，

HG′(v)=HG1′(v)+HG2′(v)+HG3′(v)≤HG1(v)+HG2(v)+HG3(v)=HG(v)

從而H(G′)≤H(G)，證畢。

3.5 變換5：圈結構變換

設G∈μk(n)，G中各圈的圈長均為g=3，各圈上至多有1條懸掛路。移動G中圈的相對位置或改變圈與圈、圈與路上點之間的距離，會改變圖G的Harary指數值。

3.5.1 雙圈圖

設G∈μ2(n)，G中兩圈的圈長均為g=3，如圖7(a)所示，兩圈位于路徑兩端。移動其中一圈的位置，改變兩圈結構使兩圈有一條合邊，其余點構成一條懸掛路，端點為一個2度點得到的圖記為G′，稱G′是由G經過圈結構變換得到的圖。

3.5.2 三圈圖

圖7 移圈變換

引理11 設G′是由G經過移圈變換得到的圖，則H(G′)≤H(G)。

證明兩種情形證明過程類似，考慮(a)類。

設G是一個如圖7所示的雙圈圖，G′是由G經過變換5得到。考慮到變換前后只有一個點v0的Harary指數改變，則有

證畢。

4 應用

定理1 設G∈μ3(n)，圖G經過上述5種變換后可得到如圖8中G1所示的極小Harary指數圖。

圖8 G1

圖G1的Harary指數為

證明根據文獻[12]，三圈圖中圈與圈的結構形式見圖9，其中，圖a1～a6經過前,種變換后能得到相似結構的圖，如圖10所示。

圖9 三圈圖中圈與圈的結構形式

圖10 經過前,種變換后得到的相似結構的圖

以a1、a5為例，變換得到的結構圖見圖11。

圖11 a1,a5變換實例

圖b1～b9經過5種變換后能得到相似結構的圖，如圖12所示。

圖12 b1～b9變換實例

以b1、b9為例，變換得到的結構圖見圖13。

圖13 b1、b9變換實例

對Ga和Gb繼續做圈結構變換可推出三圈圖的極小Harary指數圖G1，見圖14。

圖14 三圈圖的極小Harary指數圖

證畢。

5 猜想

雙圈圖的極小Harary指數圖運用上述圖變換推出所得極圖如下：

圖15 極圖示例

觀察單圈、雙圈與三圈圖的極小Harary指數圖發現：當n較大時，圈的圍長都是最終縮小至g=3，之后關于圈的相對位置進行組合使得圖的直徑盡可能大，故而猜測階為n、邊數為m的連通多圈圖的極小Harary指數圖為所有誘導圈的長度為3且直徑最大的圖。

[2] GUTMAN I.A property of the Wiener number and its modifications[J].Indian J.Chem.,1997,36A:128-132.

[5] XU K,DAS K C.Extremal Unicyclic and Bicyclic Graphs with Respect to Harary Index[J].Asian Academy of Management Journal of Accounting & Finance,2013,36(2):373-383.

[8] AI C,YU G,FENG L.The Harary index of trees[J].Utilitas Mathematica,2011,87(3):21-31.

[9] XU K,DAS K C.On Harary index of graphs [J].Discrete Applied Mathematics,2011,159(15):1631-1640.

[10] XI L F.Lipschitz equivalence of dust-like self-similar sets[J].Mathematische Zeitschrift,2010,266(3):683-691.

[11] LI S,LI X,ZHU Z.On tricyclic graphs with minimal energy[J].Match Communications in Mathematical & in Computer Chemistry,2008,59(2):397-419.

[12] 李小新,查淑萍,范益政.連通圖的Harary指數上界及其極圖[J].中國科學技術大學學報,2014,44(2):96-100.

[13] 蔡改香,余桂東,邢抱花.具有k個懸掛點的n階單圈圖的Harary指數[J].華東師范大學學報(自然科學版),2015(1):120-125.

[14] 邢抱花.關于雙圈圖的Harary指數[J].菏澤學院學報,2015(5):14-16.