周后卿，周 琪

（1.邵陽(yáng)學(xué)院數(shù)學(xué)系，湖南邵陽(yáng)422004；2.湖南農(nóng)業(yè)大學(xué)經(jīng)濟(jì)學(xué)院，長(zhǎng)沙410128）

電阻距離這個(gè)概念最早是由Klein和Randic［1］提出的.設(shè)G是一個(gè)簡(jiǎn)單連通圖，其頂點(diǎn)標(biāo)號(hào)為｛v1，v2，…，vn｝，如果G中的每條邊用單位電阻來(lái)代替，則相應(yīng)地構(gòu)造出了一個(gè)電網(wǎng)絡(luò)N.頂點(diǎn)vi和vj之間的電阻距離定義為N中vi和vj之間的有效電阻值，它是根據(jù)歐姆定律和Kirchhoff法則計(jì)算出來(lái)的，記作rij.Klein和Randic定義Kirchhoff指標(biāo)為G中所有點(diǎn)對(duì)之間的電阻距離之和，記為指標(biāo)在許多領(lǐng)域都有應(yīng)用：在化學(xué)上，它已被確定為一個(gè)用于鑒別不同分子具有相似的形狀和結(jié)構(gòu)的參數(shù)［2］；在物理和工程上，電網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間的有效電阻的計(jì)算問(wèn)題，一直是多年以來(lái)電路理論研究中的中心問(wèn)題［3］；在生態(tài)學(xué)上，電阻距離用來(lái)預(yù)測(cè)復(fù)雜景觀中的平衡遺傳結(jié)構(gòu)［4］；在數(shù)學(xué)上它是圖的一種新型距離函數(shù)，是圖的一個(gè)不變量.

近幾年來(lái)，關(guān)于Kirchhoff指標(biāo)的研究有大量的文獻(xiàn)［5－9］，得到了一批有意義的結(jié)論.對(duì)于完全圖Kn和圈Cn，文獻(xiàn)［10］證明了

對(duì)于n個(gè)頂點(diǎn)的連通圖G有

左邊的等號(hào)成立當(dāng)且僅當(dāng)G＝Kn，右邊的等號(hào)成立當(dāng)且僅當(dāng)G＝Pn，這里Kn，Pn分別表示n階完全圖和路圖.

關(guān)于Kirchhoff指標(biāo)的下界，在文獻(xiàn)［11，12］中，Zhou B等人利用圖的結(jié)構(gòu)參數(shù)，如頂點(diǎn)數(shù)，邊數(shù)，最大度，連通度和色數(shù)等得到了圖的Kirchhoff指標(biāo)的下界，

等號(hào)成立當(dāng)且僅當(dāng)G＝Kn或G＝Sn，Δ表示頂點(diǎn)的最大度，Sn表示具有n個(gè)頂點(diǎn)的星圖.他們還證明了

等號(hào)成立當(dāng)且僅當(dāng)G＝（K1∪Kn－κ－1）＋Kκ，κ表示連通度.

若圖不連通，其位于不同分支上的兩點(diǎn)之間的電阻距離被定義為無(wú)窮大，因而它的Kirchhoff指標(biāo)也就不存在.

在過(guò)去的幾十年里，循環(huán)圖出現(xiàn)在編碼理論，VLSI設(shè)計(jì)，Ramsey理論，并行計(jì)算和分布式計(jì)算中，也用于電信網(wǎng)絡(luò)里，早在上世紀(jì)90年代，文獻(xiàn)［13］就利用循環(huán)圖構(gòu)造出可靠且經(jīng)濟(jì)的通訊網(wǎng)絡(luò).同樣整循環(huán)圖在模擬量子自旋網(wǎng)絡(luò)支持的完美狀態(tài)轉(zhuǎn)移中發(fā)揮重要作用.近年來(lái)以循環(huán)圖為拓?fù)渚W(wǎng)絡(luò)的互連方案也有大量的研究.互連網(wǎng)絡(luò)的設(shè)計(jì)有兩個(gè)固有的基本限制：網(wǎng)絡(luò)中每個(gè)元件的接口數(shù)是有限的；數(shù)據(jù)傳輸過(guò)程中通過(guò)的中間點(diǎn)數(shù)必須盡可能地少.而循環(huán)網(wǎng)絡(luò)具有對(duì)稱性，結(jié)構(gòu)簡(jiǎn)單性和容易擴(kuò)充性，它的直徑和平均距離小，提高了網(wǎng)絡(luò)的可靠性，使得信息傳輸更暢通.因此，循環(huán)網(wǎng)絡(luò)被廣泛用于分布式處理系統(tǒng)，局部網(wǎng)中.正是由于循環(huán)圖的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有良好的應(yīng)用背景，所以，循環(huán)圖的研究受到了計(jì)算機(jī)領(lǐng)域的專家學(xué)者們的重視［14－15］.

本文利用循環(huán)圖的Laplacian譜，得到了循環(huán)圖的Kirchhoff指標(biāo)的一個(gè)下界；利用Euler函數(shù)和Mobius函數(shù)探討整循環(huán)圖的Kirchhoff指標(biāo)，得到了整循環(huán)圖的Kirchhoff指標(biāo)的一個(gè)簡(jiǎn)便計(jì)算公式.

1 有關(guān)循環(huán)圖的背景知識(shí)

圖G稱為循環(huán)圖，如果它的鄰接矩陣是一個(gè)循環(huán)矩陣，它是循環(huán)群上的Cayley圖.圖G稱為整譜圖，如果它的鄰接矩陣的所有特征值全為整數(shù).

設(shè)G是一個(gè)n階簡(jiǎn)單連通圖，G的鄰接矩陣記為A （G），D （G）表示G的頂點(diǎn)度對(duì)角矩陣.定義G的Laplacian矩陣為L(zhǎng) （G ）＝D （G ）－A （G），顯然L （G）是一個(gè)實(shí)對(duì)稱矩陣.根據(jù)Gerschgorin定理可知L （G）的特征值是非負(fù)實(shí)數(shù)；又因?yàn)長(zhǎng) （G）的行和為0，可知0是L （G）的最小特征值，因此不妨設(shè)L （G）的特征值為μ1≥μ2≥…≥μn－1≥μn＝0.

設(shè)n為正整數(shù)，給出集合｛0，1，2，…，n－1｝的一個(gè)子集S（又叫符號(hào)集），即S?｛0，1，2，…，n－1｝，0?S，具有n個(gè)頂點(diǎn)的循環(huán)圖記為G （n，S），它是這樣一個(gè)圖：若它的任意兩個(gè)頂點(diǎn)i與j相鄰當(dāng)且僅當(dāng)i－j mod n∈S.

設(shè)循環(huán)圖G （n，S）的鄰接矩陣為

則A的特征值為［16］

也即

由于循環(huán)圖的鄰接矩陣A是一個(gè)實(shí)對(duì)稱矩陣，因此A的特征值全為實(shí)數(shù)，從而在（2）式中有.所以，循環(huán)圖的特征值為λk＝

假設(shè)S＝｛n1，n2，…，nr｝，那么循環(huán)圖G （n，S）是一個(gè)度為r正則圖，因此在c0，c1，…，cn－1中，只有r個(gè)元素等于1，其余的均為0.顯然c0＝0，從而有

其中，n1，n2，…，nr分別表示它們?cè)诰仃嘇中所處的列數(shù).

在下面的證明中，還需要以下定義.

定義1設(shè)n是正整數(shù)，n的Euler函數(shù)φ（n）定義為不大于n且與n互素的正整數(shù)的個(gè)數(shù).

定義2 Mobius函數(shù)定義為

由文獻(xiàn)［17］知，G的Kirchhoff指標(biāo)可以用下面的公式來(lái)計(jì)算

該公式巧妙地把圖的Kirchhoff指標(biāo)和Laplacian特征值聯(lián)系起來(lái)，是一個(gè)非常經(jīng)典的結(jié)論.下面計(jì)算圖的Kirchhoff指標(biāo)時(shí)，主要用到這個(gè)結(jié)論.

2 本文結(jié)論

現(xiàn)在來(lái)證明本文的主要結(jié)論.首先討論當(dāng)G是一個(gè)n階r－循環(huán)圖時(shí)，它的Kirchhoff指標(biāo)Kf（G）的下界的問(wèn)題.

定理1若G是一個(gè)n階r－循環(huán)圖，則G的Kirchhoff指標(biāo)Kf（G）滿足下列不等式

證明 設(shè)G是一個(gè)n階r－循環(huán)圖.由于循環(huán)圖也是正則圖，所以G是一個(gè)度為r的正則圖.

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

再根據(jù)文獻(xiàn)［18］，G的Laplacian特征值為μi＝r－λn－i，i＝1，2，…，n.

所以，由（4）式，G的Kirchhoff指標(biāo)Kf（G）為

例如，對(duì)于頂點(diǎn)為10的3循環(huán)圖，它具有2類不同的形式，見(jiàn)圖1和圖2（另外兩個(gè)形式的圖分別與G1，G2同構(gòu)）.通過(guò)直接計(jì)算得到G1，G2的Laplacian特征值為

圖1 頂點(diǎn)為10的3循環(huán)圖G1（10，｛1，5，9｝）Fig.1 G1（10，｛1，5，9｝），3－circulant graph on 10 vertices

圖2 頂點(diǎn)為10的3循環(huán)圖G2（10，｛2，5，8｝）Fig.2 G2（10，｛2，5，8｝），3－circulant graph on 10 vertices

代入（4）式，求得循環(huán)圖G1（10，｛1，5，9｝）和G2（10，｛2，5，8｝）的Kirchhoff指標(biāo)是

而按照（5）式計(jì)算，得到循環(huán)圖G1（10，｛1，5，9｝）和G2（10，｛2，5，8｝）的Kirchhoff指標(biāo)的下界為15，顯然Kf （G2）＞Kf （G1）＞15，不等式（5）式成立.

下面討論當(dāng)循環(huán)圖是一個(gè)整循環(huán)圖時(shí)，它的Kirchhoff指標(biāo)將會(huì)是怎樣的.

在文獻(xiàn)［19］中，So描繪了循環(huán)圖是整循環(huán)圖所具有的特征.令

Gn（d）＝表示所有小于n的正整數(shù)集合，且與n有相同的最大公約數(shù)d.So證明了對(duì)某些約數(shù)集D?Dn，一個(gè)循環(huán)圖G （n，S）是整循環(huán)圖當(dāng)且僅當(dāng)符號(hào)集S＝這里Dn表示n的正約數(shù)d的集合，

對(duì)于n≥2，定義Ramanujan和為Rn（k）＝

由文獻(xiàn)［20］知Ramanujan公式：

這里，φ（n）是Euler函數(shù)，φ（n）＝Rn（0）＝

表示Mobius函數(shù)，μ（n）＝Rn（1）.

規(guī)定gcd （0，n）＝n，φ（1）＝1＝μ（1）.

由于對(duì)n的任何約數(shù)d，都有

因此，得到本文的另一個(gè)結(jié)論：

定理2若圖G是一個(gè)具有符號(hào)集S＝Gn（d）的n階整循環(huán)圖，.則G的Kirchhoff指標(biāo)的計(jì)算公式為：為某個(gè)素?cái)?shù)的平方所整除；

當(dāng)…p

注意到φ（1）＝1，

這樣可推出

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

從而根據(jù)（4）式得到G的Kirchhoff指標(biāo)的計(jì)算公式為

現(xiàn)舉例說(shuō)明定理的可行性.對(duì)于頂點(diǎn)為20整循環(huán)圖G （20，S），由于20的約數(shù)d只能為1，2，4，5，10，故D20＝｛1，2，4，5，10｝.若取D＝｛2｝?D20，即d＝2，則

因此由

從而

于是，得到循環(huán)圖G 20，（S）的Laplacian特征值

所以，整循環(huán)圖G 20，（S）的Kirchhoff指標(biāo)為

又通過(guò)直接計(jì)算，得到循環(huán)圖G （20，S）的譜為Spec （G （20，S））＝｛4（2），1（8），－1（8），－4（2）｝，于是得出它的Laplacian譜為｛8（2），5（8），3（8），0（2）｝，與上面結(jié)果一樣.

從此例看出，用定理2計(jì)算和直接計(jì)算結(jié)果一致.定理2的優(yōu)點(diǎn)還在于，在計(jì)算整循環(huán)圖的Kirchhoff指標(biāo)時(shí)，只要知道n的約數(shù)d，便可利用Euler函數(shù)和Mobius函數(shù)求出圖的特征值，進(jìn)而求出Kirchhoff指標(biāo)，這是一個(gè)簡(jiǎn)單而切實(shí)可行的方法.

［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］ 周永生.用循環(huán)圖構(gòu)造可靠通訊網(wǎng)絡(luò)［J］.應(yīng)用數(shù)學(xué)，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］ 徐俊明.組合網(wǎng)絡(luò)理論［M］.北京：科學(xué)出版社，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.