循環圖的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.