周 后 卿

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

?

循環(huán)圖的預(yù)解Estrada指標(biāo)

周 后 卿

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

循環(huán)圖；整循環(huán)圖；預(yù)解Estrada指標(biāo)；特征值

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

0　引　言

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

圖的預(yù)解Estrada指標(biāo)在測量復(fù)雜網(wǎng)絡(luò)中心度時(shí)具有重要作用,許多學(xué)者對其進(jìn)行了研究.CHEN等[1]討論了EEr(G)的下界問題,得到:

文獻(xiàn)[2]推出了一個計(jì)算預(yù)解Estrada指標(biāo)的公式：

對任何一個具有n個頂點(diǎn)的非完全圖G,其預(yù)解Estrada指標(biāo)為

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

文獻(xiàn)[2]還證明了,若圖G去掉一條邊e后,其預(yù)解Estrada指標(biāo)就會下降,即

EEr(G-e)

從而得到完全圖的預(yù)解Estrada指標(biāo)最大.

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

在具有n(n≥1)個頂點(diǎn)的所有連通圖中,路圖的預(yù)解Estrada指標(biāo)最小.

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

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

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

循環(huán)圖具有重要的互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),同步性與穩(wěn)定性很好,是點(diǎn)可遷圖.設(shè)循環(huán)圖G(n,S)的鄰接矩陣為

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

即

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

設(shè)S={l1,l2,…,lk}(l1

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

0≤r≤n-1.

(1)

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

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

文獻(xià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)圖的預(yù)解Estrada指標(biāo).首先有下列定理.

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

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

不妨設(shè)λ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)的預(yù)解Estrada指標(biāo)

例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)的預(yù)解Estrada指標(biāo)

21.54.

本文只討論了度為偶數(shù)時(shí)循環(huán)圖的預(yù)解Estrada指標(biāo)情況.度為奇數(shù)時(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.

湖南省教育廳科學(xué)研究項(xiàng)目(15C1235);邵陽市科技局科技計(jì)劃項(xiàng)目(2015JH41).

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

10.3785/j.issn.1008-9497.2016.05.003

O 157.5

A

1008-9497(2016)05-517-04