线性四角链及四角莫比乌斯图的Kirchhoff指标

王广富，鲁玖环

（华东交通大学理学院，江西南昌330013）



线性四角链及四角莫比乌斯图的Kirchhoff指标

王广富，鲁玖环

（华东交通大学理学院，江西南昌330013）

摘要：图G的Kirchhoff指标是指图G的所有点对之间的电阻距离之和。主要研究了线性四角链及四角莫比乌斯图的Kirchhoff指标。根据拉普拉斯多项式分解定理、Kirchhoff指标和拉普拉斯特征值之间的关系以及矩阵分解定理等得到线性四角链及四角莫比乌斯图的Kirchhoff指标计算公式；最后，通过举例直接利用欧姆定律所得Kirchhoff指标对所求公式加以验证。

关键词：电阻距离；Kirchhoff指标；拉普拉斯矩阵；线性四角链；四角莫比乌斯图

1993年，Klein和Randic提出了关于图的电阻距离的概念[1]，把图G中的每条边都设为单位电阻，构造出一个电网络N，由欧姆定律，定义图G中两个顶点i和j的电阻距离rij为电网络N中i和j这两个节点之间的总电压与总电流的比值，即i和j两个节点之间的有效电阻，图G的Kirchhoff指标就是指G的各顶点之间的电阻距离之和。它的研究在各个方面都有重要意义，例如，在化学上，对Kirchhoff指标已有广泛的研究。文献[2]利用距离矩阵和电阻距离矩阵研究了四种多环的循环图：包含5长圈的5阶图，代表柏拉图多面体的Schlegel图，巴克敏斯特富勒烯同分异构体和C70同分异构体，根据它们的循环性再依照Kirchhoff指标排序；文献[3]运用福斯特定理、随机游动、叠加原理得到特定的连通图的电阻距离或Kirchhoff指标的表达式；文献[4]根据拉普拉斯谱和特征向量得到循环图的Kirchhoff指标公式。在数学上，Kirchhoff指标在图论中也占据了重要位置，但直接计算电阻距离和Kirchhoff指标还是很困难的，所以得到Kirchhoff指标公式十分必要。文献[5]利用欧拉函数和莫比乌斯函数，得到了一个关于整循环图的Kirchhoff指标的简便计算公式；文献[6]根据图的拉普拉斯谱理论，得到了三类由按特定方式粘贴的完全图构成的特殊弦图的Kirchhoff指标公式。本文主要研究线性四角链及四角莫比乌斯图的Kirchhoff指标，逐步运用矩阵分解定理等方法来求得仅用四边形个数表达的Kirchhoff指标计算公式。

1　预备知识

本文所研究的线性四角链及四角莫比乌斯图是连通的无向图。用V和E分别表示图G的顶点集合和边集合，设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的邻接矩阵。

假设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′是同构的，称f是一个同构。f为一个自同构圳G=G′。

设G是n个顶点的连通图且其拉普拉斯矩阵为L，L的特征多项式就定义为PL（x）=det（xIn-L），这里In表示n阶单位矩阵，称这个多项式为图G的拉普拉斯多项式。

设G的拉普拉斯特征值，也就是多项式PL（x）的根为λ0，λ1，…，λn-1，假设λ0是最小的拉普拉斯特征值，则有λ0=0，并且对k＞0，λk＞0[7]，图G的拉普拉斯谱S（G）定义为所有λi，i=0，…，n-1的集合，即

有如下定理：

定理1[8-9]对任意n阶连通图G，n≥2

设Tn表示由n-1个四边形组成的一个线性四角链，Mn为一个长度为n的四角莫比乌斯图，Tn和Mn如图1和图2所示。

图1　Tn及其标号Fig.1 Tnand its labeling

图2　Mn及其标号Fig.2 Mnand its labeling

文献[10]利用图的卡氏积和循环图的Kirchhoff指标公式得到线性四角链及四角莫比乌斯分子图的Kirchhoff指标。本文则首先介绍了拉普拉斯多项式分解定理，显然，Tn和Mn有2n个特征值，根据拉普拉斯多项式分解定理，将Tn的拉普拉斯多项式分解为路Pn的拉普拉斯多项式和一个n阶矩阵的特征多项式的乘积。同理，将Mn的拉普拉斯多项式分解为圈Cn的拉普拉斯多项式和一个n阶矩阵的特征多项式的乘积。再依据第二个多项式中的根与系数的关系，分别求出Tn和Mn剩余的n个特征值的倒数和。接下来根据定理1可以得到Tn和Mn的Kirchhoff指标公式。

文中未加说明的记号以及定义等参见文献[11]。

2　拉普拉斯多项式分解

设π是图G的一个自同构。如果π能够表示成以下形式

π=（1°）（2°）…（m°）（1，1′）（2，2′）…（k，k′）（4）其中：（1°）…（m°），（1，1′）…（k，k′）是不相交的1-圈和对换，则m+2k=｜V｜有。记

对图G中的顶点排序，则L能表示成以下分块矩阵：

其中：LViVj是Vi中的顶点对应的行和Vj中的顶点对应的列构成的子矩阵，i，j=0，1，2，记

杨玉良和于同隐[12]得到了拉普拉斯多项式分解定理，在这里用文献[13-14]中的方式来叙述：

定理2设L，LA和LS为以上定义的矩阵，则PL（x）=PLA（x）PLS（x），其中PLA（x）和PLS（x）分别为矩阵LA矩阵LS的特征多项式。

特别地，如果V0=准，则

3　线性四角链的Kirchhoff指标

设Tn顶点及其标号如图1所示，显然可知π=（1，1′）（2，2′）…（n，n′）是Tn的一个自同构，因此V1={1，2，…，n}，V2={1′，2′，…，n′），对应地，LV1V1（＝LV2V2）和LV1V2如下：

根据定理2，PL（x）=PLA（x）PLS（x），故Tn的拉普拉斯谱由LA和LS的特征值构成，显然LA是路Pn的拉普拉斯矩阵，因而LA的特征值[15]为

记LS的特征值为μj，j=1，2，…，n则

设

则有下述定理:

定理3

证明由定理1

由于

又

定理得证。

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

参考文献[13]的计算方法可得

记LS的对角元为lii，i=1，2，…，n，则

令

显然

由此可得

定理4

考察Kf（Tn)的渐近性质，显然，当n→∞时，Kf（Tn)→，与文献[10]所得结果相同。而在文献[10]中

显然，公式（22）比公式（23）更加简便。

4　四角莫比乌斯图的Kirchhoff指标

Mn中的顶点标号如图2。显然π=（0，0′）（1，1′）…2n－1，2n－1 2′2是Mn的一个自同构，因此，V1＝｛0，1，2，…，n－1｝，V2＝｛0′，1′，2′，…，2n－1 2′｝。对应地，LV1V12=LV2V22和LV1V2

如下：

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

设μj，j=1，2，…，n表示LS的特征值，则根据定理2，显然Mn的拉普拉斯谱

设

则有如下定理：

定理5

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

与前面计算类似，可得

显然

由此可得

定理6

考察Kf（Mn）的渐近性质，易证，当n→∞时，Kf（Mn)→

，与文献[10]所得结果相同。而在文献[10]中

显然，公式（32）比公式（33）更加简便。

5　实例验证

例1当n=2时，T2即为C4，如图3所示。

由于

结论成立。

例2四角莫比乌斯图M2如图4所示。

图3　T2Fig.3　T2

图4　M2Fig.4 M2

由欧姆定律

又

故M2的电阻距离之和为rcd+rab+rbd+rcb+rad+rac=×6=3。又

结论得证。

[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]周后卿，周琪.循环图的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]张先迪，李正良.图论及其应用[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—），男，副教授，博士，研究方向为图论及其应用。

基金项目：国家自然科学基金（11261019,11361024）；江西省自然科学基金（2015BAB201002）；江西省教育厅科学研究项目（GJJ14380）；江西高校科技落地计划项目（KJLD12067）

收稿日期：2015－07-27

文章编号：1005-0523（2016）01-0128-08

中图分类号：O157.5

文献标志码：A