圖的基爾霍夫指數(shù)的下界

喻瑩瑩，高珊

(1.湖北大學數(shù)學與統(tǒng)計學學院，湖北 武漢 430062；2.湖北大學計算機與信息工程學院，湖北 武漢 430062；3.應用數(shù)學湖北省重點實驗室(湖北大學)，湖北 武漢430062)

0 引言

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

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

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

點v到圖G中其余所有點的電阻距離之和,定義為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]

圖

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

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

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

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

引理2[6]設圖G1,G2是兩個連通圖,令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]設圖G是一個連通圖,x是圖G的割點,令G1和G2分別是G-x兩個的連通分支,則對于任意的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對任意的星塊圖G=S[n1,n2,…,nk]，我們有

(1)

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

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

又由引理2和引理3可知

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

2 主要結(jié)果

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

令Bn,k={G:G是一個有k個塊的n階連通圖}.注意到Bn,1={Kn}.因此下面可以假設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ù)的關系可知: