馬婷妍，王維忠

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

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

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

本文僅考慮簡(jiǎn)單的無向圖。設(shè)圖G=(V,E)的頂點(diǎn)集和邊集分別為V={1,2,…,n}和E={e1,e2,…,em}，并設(shè)DG=diag(d1,d2,…,dn)是圖G的度對(duì)角矩陣，其中di(1≤i≤n)為頂點(diǎn)i的度。圖G的鄰接矩陣AG=(aij)n×n定義如下：若頂點(diǎ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的點(diǎn)-邊關(guān)聯(lián)矩陣，若頂點(diǎn)i與邊ej關(guān)聯(lián)，則bij=1；否則bij=0。

1 預(yù)備知識(shí)

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

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

引理2[14]設(shè)G1為n1個(gè)頂點(diǎn)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同時(shí)可得

(6)

由于BG11=π，所以

(7)

又因?yàn)?/p>

(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為正則圖時(shí)，得到如下關(guān)于剖分-邊聯(lián)圖G1G2的Kirchhoff指標(biāo)計(jì)算公式。

定理2.3 設(shè)G1為n1個(gè)點(diǎn)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)

下面計(jì)算式(13)中的每一項(xiàng)，注意到矩陣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)計(jì)算上式中的每一項(xiàng)，由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)用實(shí)例

這進(jìn)一步驗(yàn)證了定理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)計(jì)算可得圖P2P2的Laplacian矩陣的{1}-可逆矩陣

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

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

4 結(jié) 語

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