喻瑩瑩，高珊

(1.湖北大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院，湖北 武漢 430062；2.湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，湖北 武漢 430062；3.應(yīng)用數(shù)學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室(湖北大學(xué))，湖北 武漢430062)

0 引言

設(shè)G=(V(G),E(G))是一個(gè)有限的簡單無向圖,G中頂點(diǎn)數(shù)|V(G)|稱為圖G的階數(shù).對(duì)圖G的任意頂點(diǎn)x,G-x是指從G中刪除頂點(diǎn)x后得到的圖,G-xy是指從G中刪除邊xy后得到的圖.設(shè)G是連通圖,如果G-x不連通,那么頂點(diǎn)x成為G的的割點(diǎn)或分離點(diǎn).圖G的極大不可分離圖稱為G的塊(block).圖G的每一個(gè)階數(shù)至少為3的塊是2-連通的.如果連通圖G的每個(gè)塊都是完全圖,則稱G是塊圖.n階完全圖和n階星圖分別記為Kn和Sn.

圖G中頂點(diǎn)u到頂點(diǎn)v的最短路的長度稱為頂點(diǎn)u與v間的距離,記為dG(u,v).圖G中頂點(diǎn)u到頂點(diǎn)v的有效電阻距離記為rG(u,v).圖G的基爾霍夫指數(shù)Kf(G)定義為

Kf(G)=∑u,v∈V(G)dG(u,v).

點(diǎn)v到圖G中其余所有點(diǎn)的電阻距離之和,定義為Kfv(G)=∑u≠vr(v,u),記為Kfv(G).在不引起混淆的情況下,常用d(u,v),r(u,v)來代替dG(u,v),rG(u,v).

圖1 S[n1,n2,…,nk]

圖

設(shè)G是一個(gè)連通圖,G1和G2是G的兩個(gè)非空連通子圖,若V(G1)∩V(G2)={x},則記G=G1xG2.本文中沒有給出的符號(hào)和概念可參考文獻(xiàn)[8-9].

1 基爾霍夫指數(shù)的性質(zhì)

本節(jié)中我們給出了圖基爾霍夫指數(shù)的基本性質(zhì)及相關(guān)運(yùn)算,這些性質(zhì)和運(yùn)算在本文中主要結(jié)論的證明中經(jīng)常用到.

引理1[10]設(shè)圖G=(V(G),E(G))是非完全圖.若uv?E(G),則有Kf(G+uv)

引理2[6]設(shè)圖G1,G2是兩個(gè)連通圖,令G=G1xG2,其中V(G1)∩V(G2)={x},則有

Kf(G)=Kf(G1)+Kf(G2)+(|V(G1)|-1)Kfx(G2)+(|V(G2)|-1)Kfx(G1).

引理3[11]設(shè)圖G是一個(gè)連通圖,x是圖G的割點(diǎn),令G1和G2分別是G-x兩個(gè)的連通分支,則對(duì)于任意的a∈V(G1),b∈V(G2),均有rG(a;b)=rG1(a;x)+rG2(x;b).

引理4[10]n階完全圖的基爾霍夫指數(shù)具有下列性質(zhì)：

1)Kf(Kn)=n-1；

命題5對(duì)任意的星塊圖G=S[n1,n2,…,nk]，我們有

(1)

命題5的證明對(duì)k歸納證明(1)式.當(dāng)k=1時(shí),S[n1,n2,…,nk]=Kn1,則由引理4可知Kf(G)=n1-1,即(1)式成立.當(dāng)k=2時(shí),則由引理2和引理3可知

即(1)式成立.假設(shè)2≤k

又由引理2和引理3可知

即k=l時(shí),(1)式成立,從而

2 主要結(jié)果

本節(jié)中我們研究具有k個(gè)塊的n階連通圖的基爾霍夫指數(shù).

令Bn,k={G:G是一個(gè)有k個(gè)塊的n階連通圖}.注意到Bn,1={Kn}.因此下面可以假設(shè)k≥2.在給出我們的主要結(jié)果之前，先證明如下的引理.

圖3 G，G′，G″

引理6的證明由引理2可知

于是

=(|V(H2)|-1)[Kfx2(G0)+r(x2,x1)(n(H1)-1)+Kfx1(H1)-Kfx1(G0)-Kfx1(H1)]

=(|V(H2)|-1)[Kfx2(G0)-Kfx1(G0)+r(x2,x1)(|V(H1)|-1)]

(2)

類似地，可得

Kf(G)-Kf(G″)=(|V(H1)|-1)[Kfx1(G0)-Kfx2(G0)+r(x1,x2)(|V(H2)|-1)]

(3)

如果Kfx2(G0)≥Kfx1(G0),則由(2)式及r(x2,x1)>0,|V(H1)|≥2可知:Kf(G)>Kf(G′).

如果Kfx1(G0)≥Kfx2(G0),則由(3)式及r(x1,x2)>0,|V(H2)|≥2可知:Kf(G)>Kf(G″).

接下來證明下面的論斷.

推論1G=S[n1,n2,…,nk],這里n1+n2+…+nk=n+k-1.

圖4 G

由調(diào)和平均數(shù)與算數(shù)平均數(shù)的關(guān)系可知: