整循環圖的能量

周后卿，周 琪

（1.邵陽學院數學系，湖南 邵陽422004；2.湖南農業大學經濟學院，湖南 長沙410128）

0 引言

設G＝（V，E）是一個n階簡單連通圖.用A（G）表示G 的鄰接矩陣，A（G）的特征值記為λ1，λ2，…，λn，不妨設λ1≥λ2≥…≥λn.由于A（G）是一個非負不可約矩陣，所以它的所有特征值均為實數，圖G 的特征值也就是A（G）的特征值.圖G 的能量定義為G 的所有特征值的絕對值之和，即

圖的能量最早被I.Gutman引入［1］，它與量子化學之間有著緊密的聯系，對分子圖而言，能量對應著HMO 意義下的完全π電能.研究圖的能量的基本工具是源于Coulson的一個積分公式［2］：

這里φ（x）表示G 特征多項式，φ′（x）是φ（x）的導數.

利用上面這個公式，作為Coulson積分的一個推論，I.Gutman給出了森林的一個簡單能量公式：

這里，mk（G）表示G 的k 匹配的數目.

從那以后，許多學者對圖的能量做了相當廣泛而深刻的研究［3］，取得一大批有意義的結論.

例如，對于度為k的n 階正則圖G，R.Balakrishnan證明了圖G 的能量的一個上界［4］：

當G＝Kn時等式成立.

利用高斯和，I.Shparlinski給出了一個具有高能量循環圖的構造方法［5］；文獻［6］研究了Cayley圖的能量；文獻［7］討論了整循環圖的能量，給出了整循環圖Xn（1，pγ）的能量計算公式.雖然許多學者對圖的能量進行了卓有成效的研究，但還是有很多懸而未決的問題，R.A.Brualdi就提出了一些開問題，比如：具有n個頂點的圖的最大能量是多少？具有最大能量的圖是如何構造的？高能量圖的構造，超能圖的譜半徑有多大等問題［2］.本文研究整循環圖的能量計算問題.

1 基本概念

一個圖叫做循環圖，如果它是循環群上的Cayley圖，也即它的鄰接矩陣是一個循環矩陣.具有n 個頂點的循環圖記為G（n，S），它是這樣一個圖：若它的任意兩個頂點i與j 相鄰當且僅當i－j（mod n）∈S，S?｛0，1，2，…，n－1｝，n為正整數，S＝－S，0?S，集合S 叫做循環圖G（n，S）的符號集.一個圖稱為整譜圖，如果它的鄰接矩陣的特征值全是整數.為了便于表述，習慣將整循環圖記為ICGn（D）.在過去20年里，整循環圖不斷出現在編碼理論、VLSI設計、Ramsey理論、并行計算和分布式計算中，它在量子物理學中發揮著重要作用.［8］那么，循環圖具備什么樣的條件，才成為整循環圖呢？

設循環圖G（n，S）的鄰接矩陣為

根據文獻［9］可知，循環圖G（n，S）的特征值為

也即

設

是由小于n并且與n 具有相同的約數的所有正整數組成的集合，這里gcd（k，n）表示k，n 的公因數.令Dn是n 的所有不超過的正約數組成的集合，也即

W.So在文獻［10］中證明了下列定理：

定理1 一個循環圖G（n，S）是整循環圖當且僅當S＝∪d∈DGn（d），這里D?Dn.

在文獻［11］中，W.Klotz和T.Sander證明了整循環圖ICGn（D）的特征值為

其中

φ（x）表示Euler函數，即

其中p1，p2，…，pn是x 的素因數.

μ（x）表示Mobius函數，即

注意到，對n的任何因數d，下列等式成立：

因為

從而有

所以

即

并且

特別地，當n為偶數時，

不妨看一個例子.對于頂點數為20的循環圖，由于其約數組成的集合Dn＝｛1，2，4，5，10｝，若取D＝｛5｝，即d＝5.則：

同理可求

根據λk＝λn－k，得

由此可見，通過Euler函數和Mobius函數求整循環圖的特征值，簡單可行，不失為一個好方法.

2 主要結論

現在開始研究整循環圖的能量計算公式.

若圖G＝（V，E）與整循環圖ICGn（D）同構，即G?ICGn（D），則它們具有相同的特征值，因而G 與整循環圖ICGn（D）具有相同的能量.不妨設

此時

現在分n為偶數和奇數兩種情況進行討論.

情形1 若n為偶數，則

也即

情形2 若n為奇數，則

于是得到了本文主要結論：

定理2 設簡單連通圖G 與整循環圖ICGn（D）同構，D?Dn＝｛d1，d2，…，ds｝，d1，d2，…，ds為n 的約數，且則圖G 的能量為

例1 對于頂點為15的整循環圖ICG15（D），取D＝｛5｝，即d＝5.則

若利用計算軟件：Mathematica來求，則可求得循環圖ICG15（D）的譜為｛2（5），－1（10）｝.因此得到其能量為20，這個結果與上面用公式（2）計算的結果完全一致，從而也說明了公式的可行性.

［1］GUTMAN I.The energy of a graph［J］.Ber Math Stat Sekt Forschungszent Graz，1978，103：1－22.

［2］BRUALDI R A.Energy of a graph［J／OL］.［2012－01－10］，2006.http：／／www.public.iastate.edu／～lhcgben／energyB.pdf.

［3］GUTMAN I.The energy of a graph：old and new results，in：algebraic combinatorics and applications［M］.Berlin：Springer，2001：196－211.

［4］BALAKRISHNAN R.The energy of a graph［J］.Linear Algebra and its Applications，2004，387：287－295.

［5］SHPARLINSKI I.On the energy of some circulant graphs［J］.Linear Algebra and its Applications，2006，414：378－382.

［6］ILIC A.The energy of unitary Cayley graphs［J］.Linear Algebra and its Applications，2009，431：1881－1889.

［7］ILIC A，BASIC M.New results on the energy of integral circulant graphs［J］.Applied Mathematics and Computation，2011，218：3470－3482.

［8］SAXENA N，SEVERINI S，SHPARLINSKI I.Parameters of integral circulant graphs and periodic quantum dynamics［J］.Int J Quantum Inf，2007，5：417－430.

［9］D AVIS P J.Circulant matrices［M］.New York：John Wiley＆Sons，1979：80.

［10］SO W.Integral circulant graphs［J］.Discrete Mathematics，2006，306：153－158.

［11］KLOTZ W，SANDER T.Some properties of unitary Cayley graphs［J］.Electron Journal Combinatoria，2007，14：45.