幾類整循環(huán)圖的秩的界

周后卿

（邵陽學院理學院，湖南邵陽422000）

0 引 言

設圖G=(V,E)是具有n個頂點的簡單圖，V={v1,v2,…,vn}為頂點集，E為邊集。設圖G的鄰接矩陣為A，如果圖G的鄰接矩陣A是奇異矩陣，則圖G是奇異的。矩陣A的零空間記為ε0(A)={v0:A v0=0}，即方程組A v0=0的解向量構(gòu)成的空間。G的零度，即零空間ε0(A)的維數(shù)，用η(G)表示,是矩陣A的零特征值的重數(shù)。圖G的秩，用rank(G)表示，是矩陣A的秩，等于n-η(G)。圖的秩是圖的一個不變量，是反映圖固有特性的重要概念；圖的秩在物理、化學中也有應用；在控制論中，圖的秩可以用來判定線性系統(tǒng)是可控制的還是可觀察的。所以，研究圖的秩具有一定的理論意義和應用價值。

國內(nèi)外學者對圖的零度與秩進行了一些研究。CHANG等[1-3]研究了余圖的秩并探討了具有秩為4，5的圖的結(jié)構(gòu)特征；CHEN[4]分析了簡約單圈圖的秩集；蘇莉等[5]刻畫了秩為2與3的帶號圖以及秩為4的帶號二部圖。本文將探討幾類整循環(huán)圖的秩的界。

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

首先給出循環(huán)圖的定義：循環(huán)圖G(n,S)=(V,E)的頂點集V={0,1,2,…,n-1}，n為正整數(shù) ,S?{0,1,2,…,n-1}，0?S； 邊 集E={eij|i與j相鄰當且僅當i-j(modn)∈S},集合S稱為循環(huán)圖G(n,S)的符號集。例如，循環(huán)圖G(8,{2,3})是一個度為4的正則圖，見圖1。

圖1 具有8個頂點的循環(huán)圖Fig.1 The circulant graph on 8 vertices

循環(huán)圖一定是正則圖，其鄰接矩陣為循環(huán)矩陣。如果循環(huán)圖的鄰接矩陣的特征值全為整數(shù)，則稱為整循環(huán)圖。

循環(huán)圖是一類重要的互聯(lián)網(wǎng)絡拓撲結(jié)構(gòu)圖,某些網(wǎng)狀互聯(lián)網(wǎng)絡實質(zhì)上就是循環(huán)圖對應的網(wǎng)絡，循環(huán)網(wǎng)絡是雙環(huán)網(wǎng)的自然推廣,對循環(huán)圖的網(wǎng)絡應用研究已有很多。在過去幾十年中,循環(huán)圖與整循環(huán)圖不斷出現(xiàn)在編碼理論、超大規(guī)模集成電路（VLSI)設計、Ramsey理論、并行計算和分布式計算中，在量子物理學中也有重要應用[6]。

對于循環(huán)圖G(n,S)的特征值，文獻[7]給出了計算公式：

設Gn(d)={k|gcd(k,n)=d,1≤k＜n}是由小于n并且與n具有最大公約數(shù)d的所有正整數(shù)組成的集合。令D n是n的所有不超過成的集合,即1,2,…,k。

WASIN[8]證明了下列命題：

命題1一個循環(huán)圖G(n,S)是整循環(huán)圖當且

為了便于表述,習慣將整循環(huán)圖(integral circulant graphs)記為 ICGn(D)。

對于整循環(huán)圖的特征值，可以借助Ramanujan和（用R n(t)表示）來求解。

其中,φ(x)表示Euler函數(shù),若(i=1,2,…,k)為素數(shù)，ai∈Ν(i=1,2,…,k)為p i重數(shù),Ν表示正整數(shù)集，則

μ(x)表示莫比烏斯（Mobius）函數(shù)，具有下列性質(zhì)：

(i)μ(1)=1，

(ii）當n存在平方因子時,μ(n)=0，

(iii）當n為素數(shù)或奇數(shù)個不同素數(shù)之積時,μ(n)=-1，

(iv）當n為偶數(shù)個不同素數(shù)之積時,μ(n)=1。

注意到,R n(0)=|Gn(1)|=φ(n),Rn(1)=μ(n)。對n的任意因子d以及1≤i≤n-1,都有

2 引理與結(jié)論

為得到本文結(jié)論,需要以下引理。

引理1[9]設n=pqm，p,q是不同的素數(shù)，且gcd(m,pq)=1。若 λi為整循環(huán)圖 ICGm({1})具有重數(shù) ti的特征值,則 -2λi,(p-2)λi,(q-2)λi和(p+q-2λi)是整循環(huán)圖ICGn({p,q})分別具有重數(shù)(p-1)(q-1)ti,(q-1)ti,(p-1)ti和ti的特征值。

引理2[9]設n=pqrm,p,q,r是不同的素數(shù),且gcd(m,pqr)=1,若 λi為整循環(huán)圖 ICGm({1})具有重數(shù) ti的特征值,則 3λi,(3-2r)λi,(3-2p)λi,(3-2q)λi，(pq-2p-2q+3)λi，(pr-2p-2r+3)λi，(qr-2q-2r+3)λi和 (pq+pr+qr-2p-2q-2r+3)λi是整循環(huán)圖ICGn({p,q,r})分別具有重數(shù)(p-1)(q-1)(r-1)ti， (p-1)(q-1)ti， (q-1)(r-1)ti，(p-1)(r-1)ti，(r-1)ti，(q-1)ti，(p-1)ti和ti的特征值。

證明不失一般性,設ai∈Ν(i=1,2,…,t)，p1，p2,…,pt是不同的素數(shù)。對n的正因子d,設bi∈Ν(i=1,2,…,t)。由代數(shù)學知識可知,對任何整數(shù)a,b,c,若gcd(a,c)=1,則有g(shù)cd(ab,c)=gcd(b,c)。從而,若 gcd(n,t)=1,則 gcd(n,td)=gcd(n,d)。由此，可得到

現(xiàn)分2種情形討論。

情形1假設在集合{1,2,…,n-1}中有s個元素滿足gcd(n,t)=1,即gcd(n,td)=gcd(n,d)。于是,

從而,推出含0的特征值有r個，因此，整循環(huán)圖的秩rank(ICGn(D))=n-r。

綜合上述2種情形，定理1得證。

例1設n=24，因為 D24={1,2,3,4,6,8,12}，令D={1}? D24，則

那么循環(huán)圖G(24,S)就是整循環(huán)圖ICG24(D)。借助計算軟件，可求得 G(24,S)的譜為{8,42,018,-42,-8}。從而可知該整循環(huán)圖的秩為6。

再利用定理1的結(jié)果，有

其中，只有24,12,8,4含有平方因子，這樣的數(shù)共有18個，所以

即一共有18個0特征值，6個非零特征值，從而推出循環(huán)圖的秩為6。說明定理1求整循環(huán)圖的秩是精確的。

定理2設n=pqm，p,q(p＜q)是不同的素數(shù)，則整循環(huán)圖ICGn({ }p,q)的秩為（1） 當 p=2 時 ，rank(ICGn({ }p,q))≤n-(q-1)m；

（2）當p≠2時，rank(ICGn({ }p,q))≥2pq。

證明 由引理1，若整循環(huán)圖ICGm({}1)的特征 值 為 λ0≥λ1≥…≥λm-1, 重 數(shù) 分 別 為1,t1,…,tm-1的特征值，則整循環(huán)圖ICGn({ }p,q)的特 征 值 為 -2λi,(p-2)λi,(q-2)λi和 (p+q-2)λi,重數(shù)分別為 (p-1)(q-1)ti,(q-1)ti,(p-1)ti和ti。由引理1，得到整循環(huán)圖ICGn({ }p,q)的圖譜為

情形1當p=2時，特征值是0的個數(shù)至少為(q-1)(1+t1+t2+…+tm-1)。因為所有不同特征值的重數(shù)之和為n,即[(p-1)(q-1)+(p-1)+(q-1)+1](1+t1+t2+…+tm-1)=n，pq(1+t1+t2+…+tm-1)=n，所以，

從而推出零特征值的個數(shù)為(q-1)m。進一步可以推出整循環(huán)圖ICGn({p,q})的秩為

情形2若p≠2，如果整循環(huán)圖ICGm({}1)的特征值中含有0特征值，不妨設λ0＞0，λm-1=-λ0＜ 0，λk=0(1≤ k≤ m-2)，則 λm-1的 重 數(shù)tm-1=1。由引理 1，得到整循環(huán)圖 ICGn({p，q})的圖譜為

定理得證。

例2設 n=30=2×3×5，其中，p=2,q=3,m=5。

由定理2可推出整循環(huán)圖ICG30({2,3})的秩為

12≤rank(ICG30({2,3}))≤30-2×5=20 。

利用計算軟件直接求此整循環(huán)圖的特征值，得到的圖譜為{12,4,28,010,-14,-34,-82}，從而可知整循環(huán)圖的秩為20。

定理3設n=pqrm,p,q,r是不同的素數(shù),且gcd(m,pqr)=1,則整循環(huán)圖ICGn({p,q,r})的秩

rank(ICGn({p,q,r}))≥ 2pqr。

證明不妨設整循環(huán)圖ICGm({1})的特征值為λ0≥ λ1≥ …≥ λm-1,重數(shù)分別為 1,t1,…,tm-1。則由引理2，整循環(huán)圖ICGn({p,q,r})的圖譜為

因為素數(shù)p,q,r不相等，顯然，3-2r,3-2p,3-2q，pq-2p-2q+3，pr-2p-2r+3，qr-2q-2r+3，pq+pr+qr-2p-2q-2r+3不為0，因此，只需考慮 λi是否為 0。

現(xiàn)考慮一種極端情形，即λ0＞0。不妨設λm-1=-λ0＜ 0， λk=0(1≤ k≤ m-2)， 這 時tm-1=1，則整循環(huán)圖ICGn({p,q,r})的圖譜為

于是，可推出非零特征值的個數(shù)為

從而得到整循環(huán)圖ICGn({ }p,q,r)的秩

rank(ICGn({p,q,r}))≥2pqr。

定理3證畢。