極大基爾霍夫指數(shù)的塊圖

高珊，鐘秀雨，韓碩

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

0 引言

1993年, Klein和Randic在研究電網(wǎng)絡(luò)時(shí)定義了電網(wǎng)距離和基爾霍夫指數(shù).設(shè)G是一個(gè)連通圖，頂點(diǎn)集為V={u1,u2,…,un}.圖G中兩點(diǎn)ui與uj的有效電阻稱為ui與uj的電阻距離，記為rG(ui,uj).圖G的基爾霍夫指數(shù)，記為Kf(G)，定義為Kf(G)=∑i

本研究首先給出一些基本概念和記號(hào)以及圖的基爾霍夫指數(shù)的相關(guān)運(yùn)算，接著利用移接變形對(duì)圖的基爾霍夫指數(shù)進(jìn)行了研究，給出了塊數(shù)小于4的塊圖的基爾霍夫指數(shù)的上界，并刻畫了對(duì)應(yīng)的極圖.

1 圖的基爾霍夫指數(shù)的運(yùn)算

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

定義1.1設(shè)G是一個(gè)連通圖，G1，G2是G的兩個(gè)非連通子圖.如果E(G)=E(G1)∪E(G2)，V(G)=V(G1)∪V(G2)，且V(G1)∩V(G2)=x，則記G:=G1xG2，并稱x為圖G的割點(diǎn)(cut vertex或seperating vertex).

定義1.2設(shè)G是一個(gè)連通圖，如果圖G不含分離點(diǎn)，則稱G是不可分的(nonseperable)，否則是可分的(seperable).

定義1.3設(shè)G是一個(gè)圖，圖G的極大不可分離子圖稱為G的塊(block).

注記如果圖G是一個(gè)不可分離圖，則G本身就是一個(gè)塊.

定義1.4設(shè)G是一個(gè)連通圖，如果G的每個(gè)塊都是完全圖，則稱G是塊圖.

定義1.5給定一個(gè)圖G，令B={B:B是G的塊}，S={v∈V(G):v是G的割點(diǎn)}，定義一個(gè)二部圖B(G)，B和S分別是B(G)的二部劃分，且對(duì)任意的B∈B，v∈S.B與v在B(G)中有邊相連當(dāng)且僅當(dāng)v∈V(B).

定義1.6設(shè)G是一個(gè)圖，若G的塊路圖B(G)是一條路，則稱G為塊路圖.特別地，若G為塊圖，則記G=K[n1,n2,…,ni]是由i個(gè)塊Kni構(gòu)成的塊路圖，其中V(Kna)∩V(Kna+1)≠φ，1≤a≤i-1.當(dāng)i=2時(shí)，G=K[n1,n2](如圖1)；當(dāng)i=3時(shí)，G=K[n1,n2,n3](如圖2).

引理1.7[8]設(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).

引理1.8[9]設(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).

引理1.9[2]n階完全圖記為Kn，則有如下的結(jié)論：

1)Kf(Kn)=n-1；

引理1.10的證明1)令V(Kn1)∩V(Kn2)={x}(如圖1)，則由引理1.7和引理1.9可知

圖1 K[n1,n2]

Kf(K[n1,n2])=Kf(Kn1)+Kf(Kn2)+(n1-1)Kfx(Kn2)+(n2-1)Kfx(Kn1)

2)令V(Kn1)∩V(Kn2)={x1}，V(Kn2)∩V(Kn3)={x2}(如圖2)，則由引理1.7至引理1.9以及(1)可知

圖2 K[n1,n2,n3]

=Kfx2(Kn2)+∑z∈V(Kn1){x1}(rKn2(x2,x1)+rKn1(x1,z))

Kf(K[n1,n2,n3])=Kf(K[n1,n2])+Kf(Kn3)+(n3-1)Kfx2(K[n1,n2])+(n1+n2-2)Kfx2(Kn3)

證畢.

2 塊圖的基爾霍夫指數(shù)的上界

本節(jié)主要研究塊圖的基爾霍夫指數(shù)的上界.首先我們給出兩個(gè)塊圖的移接變形，通過這些運(yùn)算，給出某些塊圖的基爾霍夫指數(shù)的單調(diào)增性質(zhì).

引理2.1令H0是一個(gè)非平凡塊圖，H∶=H0xKn1，其中V(H0)∩V(Kn1)={x}，y∈V(Kn1){x}.如果記G=HxKn2(如圖3)，G′=HyKn2(如圖4)，則Kf(G)

圖3 K[nH0,n1,n2]

圖4 K[nH0,n1,n2]

引理2.1的證明由引理1.7可知

Kf(G)=Kf(H)+Kf(Kn1)+(|V(H)|-1)Kfx(Kn2)+(n2-1)Kfx(H)；

Kf(G′)=Kf(H)+Kf(Kn1)+(|V(H)|-1)Kfy(Kn2)+(n2-1)Kfy(H).

那么，

Kf(G)-Kf(G′)=(n2-1)(Kfx(H)-Kfy(H)).

由引理1.7～1.9可知

=Kfy(Kn1)+∑z∈V(H0){x}(rKn1(y,x)+rH0(x,z))

引理2.2令G0是一個(gè)非平凡塊圖，H0∶=Kn1vKn2，其中x1∈V(Kn1){v}，x2∈V(Kn2){v}.設(shè)G=H0x2G0(如圖5),G′=G0x1H0(如圖6).則當(dāng)n2≤n1時(shí)，Kf(G)≥Kf(G′)且等號(hào)成立當(dāng)且僅當(dāng)n1=n2.引理2.2的證明令a=|V(G0)|，b=|V(H0)|，則由引理1.7可知

圖5 K[n1,n2,nG0]

圖6 K[nG0,n1,n2]

Kf(G)=Kf(G0)+Kf(H0)+(a-1)Kfx2(H0)+(b-1)Kfx2(G0)，

Kf(G′)=Kf(G0)+Kf(H0)+(a-1)Kfx1(H0)+(b-1)Kfx1(G0)，

因此

Kf(G)-Kf(G′)=(a-1)(Kfx2(H0)-Kfx1(H0))

即Kf(G)≥Kf(G′)且等式成立當(dāng)且僅當(dāng)n1=n2.證畢.

注記令a1∈V(H0)且a1∈V(Kn2)，b1∈V(G0)，則通過點(diǎn)a1與點(diǎn)b1粘成點(diǎn)x2，把塊H0與塊G0連接起來得到圖5；令a2∈V(H0)且a2∈V(Kn1)，b2∈V(G0)，則通過點(diǎn)b2與點(diǎn)a2粘成點(diǎn)x1，把塊G0與塊H0連接起來得到圖6；那么當(dāng)?shù)诙€(gè)塊的點(diǎn)數(shù)增大時(shí)(圖6→圖5)，塊圖的基爾霍夫指數(shù)也隨著增大.

下面我們研究具有小于4個(gè)塊的n階連通塊圖的基爾霍夫指數(shù)的上界.

令Bn,k={G:G是一個(gè)有k個(gè)塊的n階連通塊圖}.注意到Bn,1={Kn}.因此下面可以假設(shè)k≥2.定理2.3令G∈Bn,2，則

定理2.4令G∈Bn,3，則

證畢.