周 后 卿

(邵陽學院 數(shù)學系, 湖南 邵陽 422000)

?

循環(huán)圖的預解Estrada指標

周 后 卿

(邵陽學院 數(shù)學系, 湖南 邵陽 422000)

循環(huán)圖；整循環(huán)圖；預解Estrada指標；特征值

Journal of Zhejiang University(Science Edition), 2016,43(5):517-520

0　引　言

設G是一個具有n個頂點的簡單圖,G的鄰接矩陣記為A(G).設A(G)的特征值為λ1,λ2,…,λn. 定義G的預解Estrada指標(以下用EEr(G) 表示)為

圖的預解Estrada指標在測量復雜網(wǎng)絡中心度時具有重要作用,許多學者對其進行了研究.CHEN等[1]討論了EEr(G)的下界問題,得到:

文獻[2]推出了一個計算預解Estrada指標的公式：

對任何一個具有n個頂點的非完全圖G,其預解Estrada指標為

其中Φ(G,λ)為G的特征多項式.

文獻[2]還證明了,若圖G去掉一條邊e后,其預解Estrada指標就會下降,即

EEr(G-e)

從而得到完全圖的預解Estrada指標最大.

文獻[3]也討論了具有最小預解Estrada指標的極圖問題,得到如下結(jié)果：

在具有n(n≥1)個頂點的所有連通圖中,路圖的預解Estrada指標最小.

本文主要研究循環(huán)圖、整循環(huán)圖的預解Estrada指標問題.

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

若一個圖是循環(huán)群上的Cayley圖,其鄰接矩陣是一個循環(huán)矩陣，則稱其為循環(huán)圖.具有n個頂點的循環(huán)圖記為G(n,S),S?{0,1,2,…,n-1},0?S,集合S為循環(huán)圖G(n,S)的符號集.它是這樣一個集合：若其任意2個頂點i與j相鄰,當且僅當i-j(modn)∈S,n為正整數(shù),S=-S.一個圖若其鄰接矩陣的特征值都為整數(shù)，則稱其為整譜圖.特征值全為整數(shù)的循環(huán)圖稱為整循環(huán)圖.為便于表述,習慣將整循環(huán)圖記為ICGn(D).在過去的幾十年里,循環(huán)圖已廣泛應用于編碼理論、VLSI設計、Ramsey理論、并行計算和分布式計算，在量子物理學中也有應用，并發(fā)揮了重要作用.

循環(huán)圖具有重要的互聯(lián)網(wǎng)絡拓撲結(jié)構,同步性與穩(wěn)定性很好,是點可遷圖.設循環(huán)圖G(n,S)的鄰接矩陣為

由文獻[5]可知,循環(huán)圖G(n,S)的特征值為

即

λr=a0+a1ωr+a2ω2r+…+an-1ω(n-1)r.

設S={l1,l2,…,lk}(l1

λr=ωl1r+ωl2r+…+ωlkr=

0≤r≤n-1.

(1)

并非所有的循環(huán)圖都是整循環(huán)圖.那么, 成為整循環(huán)圖應該具備什么條件？

Dn={d1,d2,…,dk},di|n,

文獻[4]證明了

對于Ramanujan和,通常用

表示.這里,φ(x)表示Euler函數(shù),即

其中p1,p2,…,pn是x的素因數(shù),φ(1)=1.

μ(x)表示Mobius函數(shù),即

μ(x)=

KLOTZ等[6]證明了整循環(huán)圖ICGn(D)的特征值為

注意到,對n的任何因數(shù)d,下列等式成立：

(2)

2　主要結(jié)論

對于循環(huán)圖,本文只討論度為偶數(shù)的循環(huán)圖的預解Estrada指標.首先有下列定理.

則G(n,S)的預解Estrada指標滿足下列不等式：

證明根據(jù)式(1),

不妨設λ0最大,顯然,λ0=2k.又由于

λ0+λ1+…+λn-1=0,

所以

λ1+λ2+…+λn-1=-2k,

則

2[(-1)l1+(-1)l2+…+(-1)lk].

對于整循環(huán)圖,研究n能夠分解為2個互素因子的情況.下面就S的幾種不同情形予以討論,得到下列結(jié)論.

定理2若n=pq,2

證明取D={p}?{1,p,q}=Dn,

Gn(p)={p,2p,…,(q-1)p},

于是,推出整循環(huán)圖G(n,S)的特征值

類似地,可得到：

定理4若n=pq,2

證明令D={p,q}?{1,p,q}=Dn,則

Gn(p)={p,2p,…,(q-1)p},Gn(q)={q,2q,

S={p,2p,…,(q-1)p,q,2q,…,(p-1)q}.

利用式(2),推出整循環(huán)圖的G(n,S)特征值為

可求得

μ(p)+μ(q),

φ(p)+μ(q),

μ(p)+φ(q),

φ(p)+φ(q).

于是,得到整循環(huán)圖G(n,S)的特征值

從而,解得G(n,S)的預解Estrada指標

例1取n=21,令D={3,7}?{1,3,7}=D21,則

G21(3)={3,6,9,12,15,18},G21(7)={7,14},

因而S=G21(3)∪G21(7)={3,6,7,9,12,14,15,18}.則G(n,S)=G(21,S)是一個整循環(huán)圖.由式(2),可得到特征值

從而求得整循環(huán)圖G(21,S)的圖譜為

Spec(G(21,S))={8,5(2),1(6),-2(12)}.于是,可推得整循環(huán)圖G(21,S)的預解Estrada指標

21.54.

本文只討論了度為偶數(shù)時循環(huán)圖的預解Estrada指標情況.度為奇數(shù)時的情況,有待下一步研究.

審稿專家提出了有益的修改建議,特此致謝！

[1]CHENXiaodan,QIANJianguo.BoundingtheresolventEstradaindexofagraph[J]. Journal of Mathematical Study,2012(2):159-166.

[2]CHEN Xiaodan, QIAN Jianguo. On resolvent Estrada index[J]. Match Commun Math Comput Chem,2015,73:163-174.

[3]IVAN G, BORIS F, CHEN X. Graphs with smallest resolvent Estrada indices[J]. Match Commun Math Comput Chem,2015,73:267-270.

[4]SO W. Integral circulant graphs[J]. Discrete Mathematics,2006,306:153-158.

[5]DAVIS P J. Circulant Matrices[M]. New York: John Wiley & Sons,1979.

[6]KLOTZ W, SANDER T. Some properties of unitary Cayley graphs[J]. The Electronic Journal Combinatorics,2007,14(1):697-714.

Resolvent Estrada index for circulant graphs.

ZHOU Houqing

(DepartmentofMathematics,ShaoyangUniversity,Shaoyang422000,HunanProvince,China)

circulant graph; integral circulant graph; resolvent Estrada index; eigenvalue

2015-12-22.

湖南省教育廳科學研究項目(15C1235);邵陽市科技局科技計劃項目(2015JH41).

周后卿(1963-)，ORCID:http://orcid.org/0000-0002-9813-1687，男，碩士，教授，主要從事組合數(shù)學研究，E-mail:zhouhq2004@163.com.

10.3785/j.issn.1008-9497.2016.05.003

O 157.5

A

1008-9497(2016)05-517-04