王廣富，魯玖環(huán)

（華東交通大學理學院，江西南昌330013）

?

線性四角鏈及四角莫比烏斯圖的Kirchhoff指標

王廣富，魯玖環(huán)

（華東交通大學理學院，江西南昌330013）

摘要：圖G的Kirchhoff指標是指圖G的所有點對之間的電阻距離之和。主要研究了線性四角鏈及四角莫比烏斯圖的Kirchhoff指標。根據(jù)拉普拉斯多項式分解定理、Kirchhoff指標和拉普拉斯特征值之間的關(guān)系以及矩陣分解定理等得到線性四角鏈及四角莫比烏斯圖的Kirchhoff指標計算公式；最后，通過舉例直接利用歐姆定律所得Kirchhoff指標對所求公式加以驗證。

關(guān)鍵詞：電阻距離；Kirchhoff指標；拉普拉斯矩陣；線性四角鏈；四角莫比烏斯圖

1993年，Klein和Randic提出了關(guān)于圖的電阻距離的概念[1]，把圖G中的每條邊都設(shè)為單位電阻，構(gòu)造出一個電網(wǎng)絡(luò)N，由歐姆定律，定義圖G中兩個頂點i和j的電阻距離rij為電網(wǎng)絡(luò)N中i和j這兩個節(jié)點之間的總電壓與總電流的比值，即i和j兩個節(jié)點之間的有效電阻，圖G的Kirchhoff指標就是指G的各頂點之間的電阻距離之和。它的研究在各個方面都有重要意義，例如，在化學上，對Kirchhoff指標已有廣泛的研究。文獻[2]利用距離矩陣和電阻距離矩陣研究了四種多環(huán)的循環(huán)圖：包含5長圈的5階圖，代表柏拉圖多面體的Schlegel圖，巴克敏斯特富勒烯同分異構(gòu)體和C70同分異構(gòu)體，根據(jù)它們的循環(huán)性再依照Kirchhoff指標排序；文獻[3]運用福斯特定理、隨機游動、疊加原理得到特定的連通圖的電阻距離或Kirchhoff指標的表達式；文獻[4]根據(jù)拉普拉斯譜和特征向量得到循環(huán)圖的Kirchhoff指標公式。在數(shù)學上，Kirchhoff指標在圖論中也占據(jù)了重要位置，但直接計算電阻距離和Kirchhoff指標還是很困難的，所以得到Kirchhoff指標公式十分必要。文獻[5]利用歐拉函數(shù)和莫比烏斯函數(shù)，得到了一個關(guān)于整循環(huán)圖的Kirchhoff指標的簡便計算公式；文獻[6]根據(jù)圖的拉普拉斯譜理論，得到了三類由按特定方式粘貼的完全圖構(gòu)成的特殊弦圖的Kirchhoff指標公式。本文主要研究線性四角鏈及四角莫比烏斯圖的Kirchhoff指標，逐步運用矩陣分解定理等方法來求得僅用四邊形個數(shù)表達的Kirchhoff指標計算公式。

1　預備知識

本文所研究的線性四角鏈及四角莫比烏斯圖是連通的無向圖。用V和E分別表示圖G的頂點集合和邊集合，設(shè)V={1，2，3，…，n}，G中的每條邊為單位電阻，則圖G的Kirchhoff指標Kf（G）=rij。

圖G的拉普拉斯矩陣L定義為圖G的度對角矩陣與鄰接矩陣之差，即其中：D是圖G的度對角矩陣，即由G的頂點的度組成的對角矩陣，記為D=diag（d1，d2，…，dn），其中d1，d2，…，dn表示圖G中各頂點的度；A是圖G的鄰接矩陣。

假設(shè)G=（V，E）和G′=（V′，E′）為兩個連通圖，如果有一個雙射f：V→V′，使得邊之間有：x→x′，y→y′，x，y∈V，x′，y′∈V′；xy∈E圳x′y′∈E′，則稱圖G和G′是同構(gòu)的，稱f是一個同構(gòu)。f為一個自同構(gòu)圳G=G′。

設(shè)G是n個頂點的連通圖且其拉普拉斯矩陣為L，L的特征多項式就定義為PL（x）=det（xIn-L），這里In表示n階單位矩陣，稱這個多項式為圖G的拉普拉斯多項式。

設(shè)G的拉普拉斯特征值，也就是多項式PL（x）的根為λ0，λ1，…，λn-1，假設(shè)λ0是最小的拉普拉斯特征值，則有λ0=0，并且對k＞0，λk＞0[7]，圖G的拉普拉斯譜S（G）定義為所有λi，i=0，…，n-1的集合，即

有如下定理：

定理1[8-9]對任意n階連通圖G，n≥2

設(shè)Tn表示由n-1個四邊形組成的一個線性四角鏈，Mn為一個長度為n的四角莫比烏斯圖，Tn和Mn如圖1和圖2所示。

圖1　Tn及其標號Fig.1 Tnand its labeling

圖2　Mn及其標號Fig.2 Mnand its labeling

文獻[10]利用圖的卡氏積和循環(huán)圖的Kirchhoff指標公式得到線性四角鏈及四角莫比烏斯分子圖的Kirchhoff指標。本文則首先介紹了拉普拉斯多項式分解定理，顯然，Tn和Mn有2n個特征值，根據(jù)拉普拉斯多項式分解定理，將Tn的拉普拉斯多項式分解為路Pn的拉普拉斯多項式和一個n階矩陣的特征多項式的乘積。同理，將Mn的拉普拉斯多項式分解為圈Cn的拉普拉斯多項式和一個n階矩陣的特征多項式的乘積。再依據(jù)第二個多項式中的根與系數(shù)的關(guān)系，分別求出Tn和Mn剩余的n個特征值的倒數(shù)和。接下來根據(jù)定理1可以得到Tn和Mn的Kirchhoff指標公式。

文中未加說明的記號以及定義等參見文獻[11]。

2　拉普拉斯多項式分解

設(shè)π是圖G的一個自同構(gòu)。如果π能夠表示成以下形式

π=（1°）（2°）…（m°）（1，1′）（2，2′）…（k，k′）（4）其中：（1°）…（m°），（1，1′）…（k，k′）是不相交的1-圈和對換，則m+2k=｜V｜有。記

對圖G中的頂點排序，則L能表示成以下分塊矩陣：

其中：LViVj是Vi中的頂點對應(yīng)的行和Vj中的頂點對應(yīng)的列構(gòu)成的子矩陣，i，j=0，1，2，記

楊玉良和于同隱[12]得到了拉普拉斯多項式分解定理，在這里用文獻[13-14]中的方式來敘述：

定理2設(shè)L，LA和LS為以上定義的矩陣，則PL（x）=PLA（x）PLS（x），其中PLA（x）和PLS（x）分別為矩陣LA矩陣LS的特征多項式。

特別地，如果V0=準，則

3　線性四角鏈的Kirchhoff指標

設(shè)Tn頂點及其標號如圖1所示，顯然可知π=（1，1′）（2，2′）…（n，n′）是Tn的一個自同構(gòu)，因此V1={1，2，…，n}，V2={1′，2′，…，n′），對應(yīng)地，LV1V1（＝LV2V2）和LV1V2如下：

根據(jù)定理2，PL（x）=PLA（x）PLS（x），故Tn的拉普拉斯譜由LA和LS的特征值構(gòu)成，顯然LA是路Pn的拉普拉斯矩陣，因而LA的特征值[15]為

記LS的特征值為μj，j=1，2，…，n則

設(shè)

則有下述定理:

定理3

證明由定理1

由于

又

定理得證。

由Kf（Pn）=[16]，故只需計算detLS和an-1。

參考文獻[13]的計算方法可得

記LS的對角元為lii，i=1，2，…，n，則

令

顯然

由此可得

定理4

考察Kf（Tn)的漸近性質(zhì)，顯然，當n→∞時，Kf（Tn)→，與文獻[10]所得結(jié)果相同。而在文獻[10]中

顯然，公式（22）比公式（23）更加簡便。

4　四角莫比烏斯圖的Kirchhoff指標

Mn中的頂點標號如圖2。顯然π=（0，0′）（1，1′）…2n－1，2n－1 2′2是Mn的一個自同構(gòu)，因此，V1＝｛0，1，2，…，n－1｝，V2＝｛0′，1′，2′，…，2n－1 2′｝。對應(yīng)地，LV1V12=LV2V22和LV1V2

如下：

易知LA是圈Cn的拉普拉斯矩陣，故LA的特征值[15]為

設(shè)μj，j=1，2，…，n表示LS的特征值，則根據(jù)定理2，顯然Mn的拉普拉斯譜

設(shè)

則有如下定理：

定理5

由Kf（Cn）=[17]，故只需要計算det LS和an-1。

與前面計算類似，可得

顯然

由此可得

定理6

考察Kf（Mn）的漸近性質(zhì)，易證，當n→∞時，Kf（Mn)→

，與文獻[10]所得結(jié)果相同。而在文獻[10]中

顯然，公式（32）比公式（33）更加簡便。

5　實例驗證

例1當n=2時，T2即為C4，如圖3所示。

由于

結(jié)論成立。

例2四角莫比烏斯圖M2如圖4所示。

圖3　T2Fig.3　T2

圖4　M2Fig.4 M2

由歐姆定律

又

故M2的電阻距離之和為rcd+rab+rbd+rcb+rad+rac=×6=3。又

結(jié)論得證。

[1] KLEIN D J，RANDILC M. Resistance distance[J]. Journal of Mathematical Chemistry，1993，12（1）：81-95.

[2] BABIC D，KLEIN D J，LUKOVITS I，et al. Resistance distance matrix：a computational algorithm and its application[J]. International Journal of Quantum Chemistry，2002，90（1）：166-176．

[3] PALACIOS J L．Closed form formulas for Kirchhoff index[J]. International Journal of Quantum Chemistry，2001，81（2）：135-140．

[4] ZHANG H P，YANG Y J. Resistance distance and Kirchhoff index in circulant graphs[J]. International Journal of Quantum Chemistry，2007，107（2）：330-339．

[5]周后卿，周琪.循環(huán)圖的Kirchhoff指標[J].華中師范大學學報：自然科學版，2014，48（2）：162-167.

[6]陳方珂，楊金博.三類特殊弦圖的Kirchhoff指標[J].大連民族學院學報，2009，11（1）：40-42.

[7] MERRIS R. Laplacian matrix of graphs: a survey[J]. Linear Algebra and its Applications，1994(197/198)：143-176.

[8] GUTMAN I，MOHAR B. The Quasi Wiener and the Kirchhoff indices coincide[J].Journal of Chemical Information and Computer Sciences，1996，36（5）：982-985.

[9] ZHU H Y，KLEIN D J，LUKOVITS I. Extensions of the Wiener number[J]. Journal of Chemical Information and Computer Sciences，1996，36（3）：420-428.

[10]楊玉軍.圖的電阻距離和Kirchhoff指標[D].蘭州：蘭州大學，2006：18-25.

[11]張先迪，李正良.圖論及其應(yīng)用[M].北京：高等教育出版社，2011：1-68.

[12] YANG Y L，YU T Y. Graph theory of viscoelasticities for polymers with starshaped,multiple-ring and cyclic multiple-ring molecules[J]. Makromolekulare Chemie，1985，186（3）：609-631.

[13] YANG Y J，ZHANG H P. Kirchhoff index of linear hexagonal chains[J]. International Journal of Quantum Chemistry，2008，108 （3）：503-512.

[14] WANG G F，XU B G. Kirchhoff index of hexagonal M biusgraphs[C]//2011 International Conference on Multimedia Technology，2011：5912-5915.

[15] ANDERSON JR W N，MORLEY T D. Eigenvalues of the Laplacian of a graph[J].Linear and Multilinear Algebra，1985，18（2）：141-145.

[16] ENTRINGER R C，JACKSON D E，SNYDER D A. Distance in graphs[J]. Czechoslovak Mathematical Journal，1976，26（2）：283-296.

[17] LUKOVITS I，NIKOLI S,TRINAJSTI N. Resistance distance in regular graphs[J]. International Journal of Quantum Chemistry，1999，71（3）：217-225.

（責任編輯姜紅貴）

Kirchhoff Index of Linear Tetragonal Chains and Tetragonal M咬bius Graphs

Wang Guangfu，Lu Jiuhuan
（School of Science，East China Jiaotong University，Nanchang 330013，China）

Abstract：The Kirchhoff index of G is the sum of resistance distances between all pairs of vertices in G. This paper studies the Kirchhoff index of linear tetragonal chains and tetragonal Mo咬bius graphs. According to the Laplacian polynomial decomposition theorem, the relationship between Kirchhoff index and the Laplacian eigenvalues, matrix decomposition theorem, this paper obtains formula for Kirchhoff index of linear tetragonal chains and tetragonal Mo咬bius graphs. Finally, it verifies the formula using two examples whose Kirchhoff indexes are obtained from Ohm's law.

Key words：resistance distance; Kirchhoff index; Laplacian matrix；linear tetragonal chains; tetragonal Mo咬bius graphs

作者簡介：王廣富（1976—），男，副教授，博士，研究方向為圖論及其應(yīng)用。

基金項目：國家自然科學基金（11261019,11361024）；江西省自然科學基金（2015BAB201002）；江西省教育廳科學研究項目（GJJ14380）；江西高?？萍悸涞赜媱濏椖浚↘JLD12067）

收稿日期：2015－07-27

文章編號：1005-0523（2016）01-0128-08

中圖分類號：O157.5

文獻標志碼：A