剖分-點聯(lián)圖和剖分-邊聯(lián)圖的Kirchhoff指標(biāo)

馬婷妍，王維忠

(蘭州交通大學(xué) 數(shù)理學(xué)院， 甘肅 蘭州 730030)

1993年，Klein等[1]提出了圖的電阻距離的概念。將圖G的每條邊用一個固定電阻代替，則對應(yīng)得到電網(wǎng)絡(luò)N，圖G的頂點i和j之間的電阻距離rij等于電網(wǎng)絡(luò)N中節(jié)點i和j之間的有效電阻，其求解過程遵循基爾霍夫法則和歐姆定律。Kirchhoff指標(biāo)Kf(G)定義為圖G的所有頂點對之間的電阻距離之和。1996年，Gutman[2]和Zhu[3]等分別證明了圖的Kirchhoff指標(biāo)與其拉普拉斯特征值之間的如下關(guān)系：

Kirchhoff指標(biāo)是分子結(jié)構(gòu)描述符，是一個重要的拓?fù)渲笜?biāo)，關(guān)于它的研究已有很多成果[4-13]，其中文獻[13]研究了R-點聯(lián)和R-邊聯(lián)圖的Kirchhoff指標(biāo)。受此啟發(fā)，本文考慮剖分-點聯(lián)和剖分-邊聯(lián)圖的Kirchhoff指標(biāo)。

本文僅考慮簡單的無向圖。設(shè)圖G=(V,E)的頂點集和邊集分別為V={1,2,…,n}和E={e1,e2,…,em}，并設(shè)DG=diag(d1,d2,…,dn)是圖G的度對角矩陣，其中di(1≤i≤n)為頂點i的度。圖G的鄰接矩陣AG=(aij)n×n定義如下：若頂點i和j相鄰，則aij=1；否則aij=0。圖G的Laplacian矩陣LG=DG-AG，其特征值為μ1≥μ2≥…≥μn=0(LG特征值的多重集就稱作圖G的Laplacian譜)。設(shè)BG=(bij)n×m是圖G的點-邊關(guān)聯(lián)矩陣，若頂點i與邊ej關(guān)聯(lián)，則bij=1；否則bij=0。

1 預(yù)備知識

為了方便，設(shè)Jn×n表示元素均為1的n階矩陣，1表示元素均為1的列向量。

圖1 G1=G2=P2時的剖分圖、剖分-點聯(lián)圖及剖分-邊聯(lián)圖

引理2[14]設(shè)G1為n1個頂點m1條邊的d-正則圖，G2為n2階圖，則G1和G2的剖分-邊聯(lián)圖G1G2的Laplacian矩陣的{1}-可逆矩陣為

其中l(wèi)(G1)為G1的線圖。

引理3[15]設(shè)G為n階連通圖，則Kf(G)=ntr(L(1)(G))-1TL(1)(G)1。

2 主要結(jié)果

證明由引理1可得

(1)

tr(A-1DG1)+tr(A-1AG1)，

(2)

(3)

同理可得

(4)

將式(2)—(4)帶入式(1)可得

(5)

由引理1同時可得

(6)

由于BG11=π，所以

(7)

又因為

(8)

(9)

(10)

同樣地，(LG2+n1I)-11=n11表明

(11)

將式(7)—(11)代入式(6)可得

(12)

結(jié)合式(5)和式(12)，由引理3可得定理2.1。

在定理2.1中，若G1為正則圖，則可得推論2.2。

其次，當(dāng)G1為正則圖時，得到如下關(guān)于剖分-邊聯(lián)圖G1G2的Kirchhoff指標(biāo)計算公式。

定理2.3 設(shè)G1為n1個點m1條邊的d-正則圖，則G1和G2的剖分-邊聯(lián)圖G1G2的Kirchhoff指標(biāo)為

其中l(wèi)(G1)為G1的線圖。

證明由引理2可得

dtr((Ll(G1)+dn2I)-1)+(2+n2)tr((LG1+dn2I)-1)+

(13)

下面計算式(13)中的每一項，注意到矩陣Ll(G1)+dn2I和LG2+dn2I的拉普拉斯特征值分別為μ1(l(G1))+dn2，…，μm1(l(G1))+dn2和μ1(G1)+dn2，…，μn1(G1)+dn2，故可得

(14)

同理可得

將式(14)—(16)代入式(13)可得

另一方面

(18)

現(xiàn)計算上式中的每一項，由1T(Ll(G1)+dn2I)=dn21T可得

(19)

同理可得

(20)

(21)

(22)

類似地，由(LG2+m1I)-11=m11可得

(23)

將式(19)—(23)代入式(18)可得

(24)

結(jié)合式(17)和式(24)，由引理3可得定理2.3。

3 應(yīng)用實例

這進一步驗證了定理2.1以及推論2.2中結(jié)論的正確性。

例2 設(shè)G1=G2=P2，則圖1(d)P2P2的Kirchhoff指標(biāo)Kf(P2P2)=38/3。

容易知道P2的拉普拉斯特征值為0和2，而其線圖的拉普拉斯特征值為0。于是由定理2.2可得圖P2P2的Kirchhoff指標(biāo)Kf(P2P2)=38/3。

另一方面，經(jīng)計算可得圖P2P2的Laplacian矩陣的{1}-可逆矩陣

由引理3可計算圖P2P2的Kirchhoff指標(biāo)

這進一步驗證了定理2.1以及推論2.2中結(jié)論的正確性。

4 結(jié) 語

本文主要借助圖的Laplacian矩陣的廣義逆矩陣，給出了兩個圖的剖分-點聯(lián)圖與剖分-邊聯(lián)圖的Kirchhoff指標(biāo)計算公式，并通過兩個簡單的實例驗證了所得結(jié)果的正確性。