基于圈圖Harary指數(shù)減小的圖變換

劉 奇，邵燕靈，胡 鵬

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

1 背景

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

設(shè)圖G是n階連通圖，圖G的Harary指數(shù)被定義為：

(1)

如果用γ(G,k) 表示圖G中距離為k的頂點(diǎn)對(duì)的數(shù)量，則

(2)

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

(3)

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

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

2 引理

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

(4)

引理2[9]n階圈Cn的Harary指數(shù)為

(5)

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

引理3[3]設(shè)G=G1vG2，則

(6)

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

引理4 設(shè)G=G1uG2vG3，結(jié)合引理3，有

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

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

(7)

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

(8)

3 5種基本圖變換

3.1 變換1：懸掛樹(shù)變換

設(shè)G是一個(gè)圈圖，其中v0是G中某個(gè)圈上的點(diǎn)，T是G中以v0為根點(diǎn)的一顆m階懸掛樹(shù)。將m階懸掛樹(shù)T變成一條以v0為一個(gè)端點(diǎn)的m階懸掛路P，得到的圖記為G′，稱G′是由G經(jīng)過(guò)懸掛樹(shù)變換得到的圖，見(jiàn)圖1。

圖1 懸掛樹(shù)變換

引理7 設(shè)G′是由G經(jīng)過(guò)懸掛樹(shù)變換得到的圖，則H(G′)

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

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

從而由引理3可知

<

證明完畢。

3.2 變換2：融懸掛路變換

3.2.1 單圈圖

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

圖2 單圈圖

3.2.2 多圈圖

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

圖3 一般形式

引理8 設(shè)G′是由G經(jīng)過(guò)融懸掛路變換得到的圖，則H(G′)

證明考慮圖2的情形：

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

第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′，此時(shí)mi, i+1≥li且mi, i+1≥li+1。將G中的懸掛路Pl2移至Pl1上，所得圖G2的Harary指數(shù)減小，重復(fù)可得G′。

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

將圖G1上懸掛路Pl2以外的頂點(diǎn)分成3部分：

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

當(dāng)m2i≤m1i時(shí)，顯然有Pl2與Pli之間點(diǎn)對(duì)的反距離減??；

當(dāng)m2i>m1i時(shí)，有m1i>m1(i+1)，Pl2與Pli之間點(diǎn)對(duì)的反距離增大，

以上3部分結(jié)合引理4有

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

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

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

同理，懸掛路Pl2移動(dòng)到Pl1的末端點(diǎn)時(shí)

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

顯然可以得出

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

3.3 變換3:圈長(zhǎng)變換

設(shè)G1，G2，G3為連通圖，G2的階為m，圈長(zhǎng)為g(g≥4)，且至多有一條懸掛路，圖G2與G1，G3分別有一個(gè)公共點(diǎn)u，v(G1，G3可為空?qǐng)D)，G=G1uG2vG3。將G2變?yōu)橛梢粋€(gè)3長(zhǎng)圈連接一條m-3長(zhǎng)懸掛路構(gòu)成的m階單圈圖G2′，其中點(diǎn)v為G2′的懸掛點(diǎn)，點(diǎn)u為G2′中3長(zhǎng)圈的一個(gè)2度點(diǎn)，記G′=G1uG2′vG3，稱G′是由G經(jīng)過(guò)圈長(zhǎng)變換得到的圖，如圖4所示。

引理9 設(shè)G′是由G經(jīng)過(guò)圈長(zhǎng)變換得到的圖，則H(G′)≤H(G)。

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

圖G′=G1uG2′vG3由G=G1uG2vG3經(jīng)過(guò)圈長(zhǎng)變換得到。由引理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))，結(jié)合引理1和引理2、3知上式中各行的值為負(fù)，可得出H(G′)-H(G)<0。證畢。

圖4 圈長(zhǎng)變換

3.4 變換4：去合邊變換

3.4.1 雙圈合邊

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

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

圖5 雙圈合邊

3.4.2 三圈合邊

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

圖6 三圈合邊

引理10 設(shè)G′是由G經(jīng)過(guò)去合邊變換得到的圖，則H(G′)≤H(G)。

證明雙圈合邊：

當(dāng)k=1時(shí)，可根據(jù)圈長(zhǎng)變換證明。

當(dāng)k≥2時(shí)，圖G經(jīng)過(guò)去合邊變換得到圖G′，結(jié)合引理3，G2的Harary指數(shù)的變化可看做兩部分。

1) 圈Cg1上的點(diǎn)對(duì)應(yīng)圈Cg2上的點(diǎn)對(duì)。記圖G中圈Cg1、Cg2經(jīng)過(guò)變換后的部分為，結(jié)合引理9中圈長(zhǎng)變換的證明可得：

2) 圈Cg1與圈Cg2間的點(diǎn)對(duì)。合邊v1v2上的點(diǎn)對(duì)變換后的距離沒(méi)有變化，合邊以外的點(diǎn)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)，結(jié)合引理3的證明可得H(G′)-H(G)<0。

三圈合邊：

記圖G中圈C1經(jīng)過(guò)變換后的部分為C1′，對(duì)于圖G中圈C1上任一點(diǎn)v，結(jié)合引理3，有Hc1′(v)≤Hc1(v)，且

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

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

情形4：設(shè)G′是由G經(jīng)過(guò)去合邊變換得到。

記圖G中路徑v0v1u1、v0v2u2、v0v3u3為P1、P2、P3，經(jīng)過(guò)變換后的部分為P1′、P2′、P3′。結(jié)合引理3，對(duì)于P1上u1以外的點(diǎn)v，有H(P1′v)≤H(P1v)且

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

考慮點(diǎn)u1、u2、u3有

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

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

此時(shí)只需證明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：圈結(jié)構(gòu)變換

設(shè)G∈μk(n)，G中各圈的圈長(zhǎng)均為g=3，各圈上至多有1條懸掛路。移動(dòng)G中圈的相對(duì)位置或改變?nèi)εc圈、圈與路上點(diǎn)之間的距離，會(huì)改變圖G的Harary指數(shù)值。

3.5.1 雙圈圖

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

3.5.2 三圈圖

圖7 移圈變換

引理11 設(shè)G′是由G經(jīng)過(guò)移圈變換得到的圖，則H(G′)≤H(G)。

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

設(shè)G是一個(gè)如圖7所示的雙圈圖，G′是由G經(jīng)過(guò)變換5得到?？紤]到變換前后只有一個(gè)點(diǎn)v0的Harary指數(shù)改變，則有

證畢。

4 應(yīng)用

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

圖8 G1

圖G1的Harary指數(shù)為

證明根據(jù)文獻(xiàn)[12]，三圈圖中圈與圈的結(jié)構(gòu)形式見(jiàn)圖9，其中，圖a1～a6經(jīng)過(guò)前,種變換后能得到相似結(jié)構(gòu)的圖，如圖10所示。

圖9 三圈圖中圈與圈的結(jié)構(gòu)形式

圖10 經(jīng)過(guò)前,種變換后得到的相似結(jié)構(gòu)的圖

以a1、a5為例，變換得到的結(jié)構(gòu)圖見(jiàn)圖11。

圖11 a1,a5變換實(shí)例

圖b1～b9經(jīng)過(guò)5種變換后能得到相似結(jié)構(gòu)的圖，如圖12所示。

圖12 b1～b9變換實(shí)例

以b1、b9為例，變換得到的結(jié)構(gòu)圖見(jiàn)圖13。

圖13 b1、b9變換實(shí)例

對(duì)Ga和Gb繼續(xù)做圈結(jié)構(gòu)變換可推出三圈圖的極小Harary指數(shù)圖G1，見(jiàn)圖14。

圖14 三圈圖的極小Harary指數(shù)圖

證畢。

5 猜想

雙圈圖的極小Harary指數(shù)圖運(yùn)用上述圖變換推出所得極圖如下：

圖15 極圖示例

觀察單圈、雙圈與三圈圖的極小Harary指數(shù)圖發(fā)現(xiàn)：當(dāng)n較大時(shí)，圈的圍長(zhǎng)都是最終縮小至g=3，之后關(guān)于圈的相對(duì)位置進(jìn)行組合使得圖的直徑盡可能大，故而猜測(cè)階為n、邊數(shù)為m的連通多圈圖的極小Harary指數(shù)圖為所有誘導(dǎo)圈的長(zhǎng)度為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指數(shù)上界及其極圖[J].中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào),2014,44(2):96-100.

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

[14] 邢抱花.關(guān)于雙圈圖的Harary指數(shù)[J].菏澤學(xué)院學(xué)報(bào),2015(5):14-16.