循环图的Kirchhoff指标

周后卿，周 琪

（1.邵阳学院数学系，湖南邵阳422004；2.湖南农业大学经济学院，长沙410128）

电阻距离这个概念最早是由Klein和Randic［1］提出的.设G是一个简单连通图，其顶点标号为｛v1，v2，…，vn｝，如果G中的每条边用单位电阻来代替，则相应地构造出了一个电网络N.顶点vi和vj之间的电阻距离定义为N中vi和vj之间的有效电阻值，它是根据欧姆定律和Kirchhoff法则计算出来的，记作rij.Klein和Randic定义Kirchhoff指标为G中所有点对之间的电阻距离之和，记为指标在许多领域都有应用：在化学上，它已被确定为一个用于鉴别不同分子具有相似的形状和结构的参数［2］；在物理和工程上，电网络中任意两个节点间的有效电阻的计算问题，一直是多年以来电路理论研究中的中心问题［3］；在生态学上，电阻距离用来预测复杂景观中的平衡遗传结构［4］；在数学上它是图的一种新型距离函数，是图的一个不变量.

近几年来，关于Kirchhoff指标的研究有大量的文献［5－9］，得到了一批有意义的结论.对于完全图Kn和圈Cn，文献［10］证明了

对于n个顶点的连通图G有

左边的等号成立当且仅当G＝Kn，右边的等号成立当且仅当G＝Pn，这里Kn，Pn分别表示n阶完全图和路图.

关于Kirchhoff指标的下界，在文献［11，12］中，Zhou B等人利用图的结构参数，如顶点数，边数，最大度，连通度和色数等得到了图的Kirchhoff指标的下界，

等号成立当且仅当G＝Kn或G＝Sn，Δ表示顶点的最大度，Sn表示具有n个顶点的星图.他们还证明了

等号成立当且仅当G＝（K1∪Kn－κ－1）＋Kκ，κ表示连通度.

若图不连通，其位于不同分支上的两点之间的电阻距离被定义为无穷大，因而它的Kirchhoff指标也就不存在.

在过去的几十年里，循环图出现在编码理论，VLSI设计，Ramsey理论，并行计算和分布式计算中，也用于电信网络里，早在上世纪90年代，文献［13］就利用循环图构造出可靠且经济的通讯网络.同样整循环图在模拟量子自旋网络支持的完美状态转移中发挥重要作用.近年来以循环图为拓扑网络的互连方案也有大量的研究.互连网络的设计有两个固有的基本限制：网络中每个元件的接口数是有限的；数据传输过程中通过的中间点数必须尽可能地少.而循环网络具有对称性，结构简单性和容易扩充性，它的直径和平均距离小，提高了网络的可靠性，使得信息传输更畅通.因此，循环网络被广泛用于分布式处理系统，局部网中.正是由于循环图的网络拓扑结构具有良好的应用背景，所以，循环图的研究受到了计算机领域的专家学者们的重视［14－15］.

本文利用循环图的Laplacian谱，得到了循环图的Kirchhoff指标的一个下界；利用Euler函数和Mobius函数探讨整循环图的Kirchhoff指标，得到了整循环图的Kirchhoff指标的一个简便计算公式.

1 有关循环图的背景知识

图G称为循环图，如果它的邻接矩阵是一个循环矩阵，它是循环群上的Cayley图.图G称为整谱图，如果它的邻接矩阵的所有特征值全为整数.

设G是一个n阶简单连通图，G的邻接矩阵记为A （G），D （G）表示G的顶点度对角矩阵.定义G的Laplacian矩阵为L （G ）＝D （G ）－A （G），显然L （G）是一个实对称矩阵.根据Gerschgorin定理可知L （G）的特征值是非负实数；又因为L （G）的行和为0，可知0是L （G）的最小特征值，因此不妨设L （G）的特征值为μ1≥μ2≥…≥μn－1≥μn＝0.

设n为正整数，给出集合｛0，1，2，…，n－1｝的一个子集S（又叫符号集），即S⊆｛0，1，2，…，n－1｝，0∉S，具有n个顶点的循环图记为G （n，S），它是这样一个图：若它的任意两个顶点i与j相邻当且仅当i－j mod n∈S.

设循环图G （n，S）的邻接矩阵为

则A的特征值为［16］

也即

由于循环图的邻接矩阵A是一个实对称矩阵，因此A的特征值全为实数，从而在（2）式中有.所以，循环图的特征值为λk＝

假设S＝｛n1，n2，…，nr｝，那么循环图G （n，S）是一个度为r正则图，因此在c0，c1，…，cn－1中，只有r个元素等于1，其余的均为0.显然c0＝0，从而有

其中，n1，n2，…，nr分别表示它们在矩阵A中所处的列数.

在下面的证明中，还需要以下定义.

定义1设n是正整数，n的Euler函数φ（n）定义为不大于n且与n互素的正整数的个数.

定义2 Mobius函数定义为

由文献［17］知，G的Kirchhoff指标可以用下面的公式来计算

该公式巧妙地把图的Kirchhoff指标和Laplacian特征值联系起来，是一个非常经典的结论.下面计算图的Kirchhoff指标时，主要用到这个结论.

2 本文结论

现在来证明本文的主要结论.首先讨论当G是一个n阶r－循环图时，它的Kirchhoff指标Kf（G）的下界的问题.

定理1若G是一个n阶r－循环图，则G的Kirchhoff指标Kf（G）满足下列不等式

证明 设G是一个n阶r－循环图.由于循环图也是正则图，所以G是一个度为r的正则图.

由（3）式可知，G的特征值为：

再根据文献［18］，G的Laplacian特征值为μi＝r－λn－i，i＝1，2，…，n.

所以，由（4）式，G的Kirchhoff指标Kf（G）为

例如，对于顶点为10的3循环图，它具有2类不同的形式，见图1和图2（另外两个形式的图分别与G1，G2同构）.通过直接计算得到G1，G2的Laplacian特征值为

图1 顶点为10的3循环图G1（10，｛1，5，9｝）Fig.1 G1（10，｛1，5，9｝），3－circulant graph on 10 vertices

图2 顶点为10的3循环图G2（10，｛2，5，8｝）Fig.2 G2（10，｛2，5，8｝），3－circulant graph on 10 vertices

代入（4）式，求得循环图G1（10，｛1，5，9｝）和G2（10，｛2，5，8｝）的Kirchhoff指标是

而按照（5）式计算，得到循环图G1（10，｛1，5，9｝）和G2（10，｛2，5，8｝）的Kirchhoff指标的下界为15，显然Kf （G2）＞Kf （G1）＞15，不等式（5）式成立.

下面讨论当循环图是一个整循环图时，它的Kirchhoff指标将会是怎样的.

在文献［19］中，So描绘了循环图是整循环图所具有的特征.令

Gn（d）＝表示所有小于n的正整数集合，且与n有相同的最大公约数d.So证明了对某些约数集D⊆Dn，一个循环图G （n，S）是整循环图当且仅当符号集S＝这里Dn表示n的正约数d的集合，

对于n≥2，定义Ramanujan和为Rn（k）＝

由文献［20］知Ramanujan公式：

这里，φ（n）是Euler函数，φ（n）＝Rn（0）＝

表示Mobius函数，μ（n）＝Rn（1）.

规定gcd （0，n）＝n，φ（1）＝1＝μ（1）.

由于对n的任何约数d，都有

因此，得到本文的另一个结论：

定理2若图G是一个具有符号集S＝Gn（d）的n阶整循环图，.则G的Kirchhoff指标的计算公式为：为某个素数的平方所整除；

当…p

注意到φ（1）＝1，

这样可推出

因此可推出G的Laplacian特征值为

从而根据（4）式得到G的Kirchhoff指标的计算公式为

现举例说明定理的可行性.对于顶点为20整循环图G （20，S），由于20的约数d只能为1，2，4，5，10，故D20＝｛1，2，4，5，10｝.若取D＝｛2｝⊆D20，即d＝2，则

因此由

从而

于是，得到循环图G 20，（S）的Laplacian特征值

所以，整循环图G 20，（S）的Kirchhoff指标为

又通过直接计算，得到循环图G （20，S）的谱为Spec （G （20，S））＝｛4（2），1（8），－1（8），－4（2）｝，于是得出它的Laplacian谱为｛8（2），5（8），3（8），0（2）｝，与上面结果一样.

从此例看出，用定理2计算和直接计算结果一致.定理2的优点还在于，在计算整循环图的Kirchhoff指标时，只要知道n的约数d，便可利用Euler函数和Mobius函数求出图的特征值，进而求出Kirchhoff指标，这是一个简单而切实可行的方法.

［1］ Klein D J，Randic M.Resistance distance［J］.J Math Chem，1993，12：81－95.

［2］ Klein D J.Resistance distance sum rules［J］.Croat Chem Acta，2002，75：633－649.

［3］ Cserti J.Application of the lattice Green′s function for calculating the resistance of an infinite network of resistors［J］.Am J Phys，2002，68：896－906.

［4］ Mcrae B H，Dicksonl B G.Using circuit theory to model connectivity in ecology，evolution and conservation［J］.Ecology，2008，89：2712－2724.

［5］ Enrique B，Angeles C，Andres M E.A formula for the eirchhoff index［J］.Int J Quan Chem，2008，108：1200－1206.

［6］ Chen H Y，Zhang F J.Resistance distance and the normalized Laplacian spectrum［J］.Disc Appl Math，2007，155：654－661.

［7］ Chen H Y，Zhang F J.Resistance distance local rules［J］.J of Math Chem，2008，44：405－417.

［8］ Babic D，Klein D J，Lukovits I.Resistance distance matrix：a computational algorithm and its application［J］.Int J Quantum Chem，2002，90：166－176.

［9］ Xiao W J，Gutman I.Resistance distance and Laplacian spectrum［J］.Theor Chem ACC，2003，110：284－289.

［10］ Lukovits I，Nikolic S，Trinajstic N.Resistance distance in regular graphs［J］.Int J Quantum Chem，1999，71：217－225.

［11］ Zhou B，Trinajestic N.A note on Kirchhoff index［J］.Chem Phys Lett，2008，455：120－123.

［12］ Zhou B，Trinajestic N.The Kirchhoff index and the matching number［J］.Int J Quantum Chem，2009，109：2978－2981.

［13］ 周永生.用循环图构造可靠通讯网络［J］.应用数学，1993，4：359－365.

［14］ Angeles－Canul R J，Norton R M.Perfect state transfer，in－tegral circulants and join of graphs［J］.Quant Inform Comput，2010，10：325－342.

［15］ 徐俊明.组合网络理论［M］.北京：科学出版社，2007.

［16］ Davis P.Circulant Matrices［M］.New York：John Wiley ＆Sons，1979.

［17］ Ravindra B B，Gutman I，Xiao W J.A simple method for computing resistance distance［J］.Z Naturforsch，2003，A58：494－498.

［18］ Cvetkovic D，Doob M，Sachs H.Spectra of Araphs：Theory and Applications［M］.3rdrevised and enlarged edition.Leipzig：J A Barth Verlag，Heidelberg，1995.

［19］ So W.Note Integral circulant graphs［J］.Discrete Mathematics，2005，306：153－158.

［20］ Ramanujan S.On certain trigonometrical sums and their applications in the theory of numbers［J］.Cambridge Phil Trans，1918，22：259－276.