田貴賢, 孫 眉

(浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

圖的譜不僅能很好地反映圖的結(jié)構(gòu)(如簡單圖恰有一個(gè)正特征值當(dāng)且僅當(dāng)它是一個(gè)完全多部圖；若圖的代數(shù)連通度大于0,則其必連通[1-2]等),而且圖的譜也可以用來研究圖的其他性質(zhì)，如圖的能量[1]、生成樹的數(shù)量[2-3]、(度)基爾霍夫指數(shù)[4-5]、整譜圖的構(gòu)造[6-7]等等.

本文主要研究核-衛(wèi)星圖和廣義核-衛(wèi)星圖的無符號(hào)拉普拉斯譜.

設(shè)G=(V,E)是一個(gè)有n個(gè)頂點(diǎn)、m條邊的無向連通簡單圖，其中頂點(diǎn)集為V，邊集為E.用di表示頂點(diǎn)vi的度，即與頂點(diǎn)vi相關(guān)聯(lián)的邊的條數(shù).圖G的鄰接矩陣A(G)=(aij)n×n是一個(gè)n階方陣，其元素滿足：若vi和vj相鄰，則aij=1；否則，aij=0.矩陣A(G)的所有特征值的集合稱為G的譜.用D(G)=diag(d1,d2,…,dn)表示圖G的度對角矩陣,稱L(G)=D(G)-A(G)為圖的拉普拉斯矩陣;稱矩陣L(G)的所有特征值的集合為G的拉普拉斯譜;稱Q(G)=D(G)+A(G)為圖G的無符號(hào)拉普拉斯矩陣;稱矩陣Q(G)的所有特征值的集合為G的無符號(hào)拉普拉斯譜.

設(shè)G1=(V1,E1)，G2=(V2,E2)是2個(gè)簡單圖.若圖G1∪G2=(V,E)的點(diǎn)集為V=V1∪V2,邊集為E=E1∪E2，則稱G1∪G2是G1與G2的并.若圖G1G2=(V,E)的點(diǎn)集與邊集分別為V=V1∪V2和E={eij|?vi∈V1,vj∈V2}∪E1∪E2，則稱G1G2是G1與G2的連圖.為簡單起見，η個(gè)G的并，記為ηG.

定義1[8]設(shè)c≥1，s≥1，η≥2.稱圖Θ(c,s,η)?Kc(ηKs)為以Kc為核團(tuán)、以η個(gè)Ks為星團(tuán)的核-衛(wèi)星圖，其中Kc表示c個(gè)點(diǎn)的完全圖.

由于在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)模型中，并非所有的星團(tuán)都相同.因此，需要進(jìn)一步考慮將核-衛(wèi)星圖推廣到具有多個(gè)不同星團(tuán)的情形.

定義2[8]設(shè)si≥1,ηi≥1,i=1,2,…,t.稱圖Θ(c,s,η)?Kc(η1Ks1∪η2Ks2∪…∪ηtKst)為廣義核-衛(wèi)星圖，其中s=(s1,s2,…,st),η=(η1,η2,…,ηt).

顯然，核-衛(wèi)星圖Θ(c,s,η)是廣義核-衛(wèi)星圖Θ(c,s,η)的特殊情形，即t=1時(shí)的情形.

近些年，運(yùn)算圖的各類譜得到廣泛研究，如Indual[6]引入了細(xì)分點(diǎn)、細(xì)分邊連圖的概念并刻畫了它們的鄰接譜與因子圖的鄰接譜之間的關(guān)系,也構(gòu)造了一些整譜圖；文獻(xiàn)[4]進(jìn)一步刻畫了細(xì)分點(diǎn)、細(xì)分邊連圖的鄰接譜，拉普拉斯譜，以及無號(hào)拉普拉斯譜與因子圖的相應(yīng)譜之間的關(guān)系，也構(gòu)造了一些同譜圖對,并計(jì)算了上述圖類生成數(shù)的數(shù)目和基爾霍夫指數(shù)；文獻(xiàn)[9]又將上述部分結(jié)果推廣到更一般的情況，即將點(diǎn)連和邊連的情況同時(shí)進(jìn)行考慮，給出了雙連圖的概念.同時(shí),也刻畫了關(guān)于細(xì)分圖、R-圖、Q-圖及全圖的雙連圖的拉普拉斯譜.最近,文獻(xiàn)[7,10]也刻畫了幾類特殊的連圖的無符號(hào)拉普拉斯譜，進(jìn)一步構(gòu)造了一些無符號(hào)拉普拉斯整譜圖.廣義核-衛(wèi)星圖是區(qū)別于文獻(xiàn)[4,6,9]中的連圖變異類的一種特殊的連圖,在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)模型中有著廣泛的應(yīng)用.Estrada等[8]研究了該圖的聚類系數(shù)、度匹配系數(shù),并通過構(gòu)造特征值及對應(yīng)的特征向量刻畫這類圖的鄰接譜和拉普拉斯譜.

受上述研究的啟發(fā)，本文將研究核-衛(wèi)星圖和廣義核-衛(wèi)星圖的無符號(hào)拉普拉斯譜.通過構(gòu)造核-衛(wèi)星圖和廣義核-衛(wèi)星圖的特征值及對應(yīng)的特征向量，得到它們的無符號(hào)拉普拉斯譜與核團(tuán)、星團(tuán)的結(jié)構(gòu)關(guān)系.作為應(yīng)用,本文也構(gòu)造了一些無符號(hào)拉普拉斯整譜圖，推廣了文獻(xiàn)[7，10]的部分相關(guān)結(jié)果.

1 廣義核-衛(wèi)星圖的無符號(hào)拉普拉斯譜

給定廣義核-衛(wèi)星圖Θ(c,s,η)，定義c×(ηisi)階矩陣

和(ηisi)×(ηisi)階準(zhǔn)對角矩陣

其中:對角塊上共有ηi個(gè)A(Ksi);i=1,2,…,t.

適當(dāng)排列廣義核-衛(wèi)星圖Θ(c,s,η)點(diǎn)的次序可以將其鄰接矩陣表示成如下的分塊形式：

Q=A+D=

定理1廣義核-衛(wèi)星圖Θ(c,s,η)的無符號(hào)拉普拉斯譜由下列特征值構(gòu)成：

2)特征值λ=si+c-2，其重?cái)?shù)為ηi(si-1)；

3)特征值λ=2si+c-2，其重?cái)?shù)為ηi-1；

4)余下特征值是下列方程的根：

證明 注意到完全圖Kc的譜為{c-1(1),-1(c-1)}，其中a(b)表示a重復(fù)b次.顯然，1c是屬于特征值c-1的特征向量.假設(shè)x1是屬于特征值-1的特征向量,令向量

(1)

其分塊方法與Q相同.那么特征方程Qx=λx等價(jià)于

令向量

(2)

其分塊方法與Q相同.那么特征方程Qx=λx等價(jià)于

λ=-1+(si-1+c).

由于Kc屬于特征值-1的線性無關(guān)的特征向量有si-1個(gè),而同一類星團(tuán)的個(gè)數(shù)為ηi,故特征值λ=si+c-2的重?cái)?shù)為ηi(si-1).

令非零向量

其中,x中的非零塊出現(xiàn)在對應(yīng)于Q中的對角線塊Ai+Di的位置上，且分塊方法與Q相同.因此，由特征方程Qx=λx可得

其中,Di1=Di2=…=Diηi=(c-1+si)Esi.從而上式等價(jià)于(A(Ksi)+Dij)1si=λ1si,j=1,2,…,ηi.故

λ=si-1+(si-1+c).

再由方程α1+α2+…+αηi=0的解空間的維數(shù)是ηi-1可得λ=2si+c-2的重?cái)?shù)為ηi-1.

最后,分2種情況討論余下的t+1個(gè)特征值 .當(dāng)t=1時(shí),該圖為核-衛(wèi)星圖Θ(c,s1,η1).令向量

其分塊方法與Q相同.由特征方程Qx=λx可得

上式表明:

2(c-1)+η1s1+βη1s1=λ;

c+β(2(s1-1)+c)=λβ.

消去β可得

進(jìn)而有

λ2-(η1s1+3c+2s1-4)λ+

(η1s1+2c-2)(c+2s1-2)-cs1η1=0.

解此二次方程可得

下面假設(shè)t>1，令向量

其分塊方法與Q相同.顯然,這種形式的向量與式(1)和式(2)中的所有特征向量都正交.對于這樣的向量，由Qx=λx可得

所以

(3)

c+βi(2si-2+c)=λβi.

(4)

整理可得,

所以

該方程決定了廣義核-衛(wèi)星圖Θ(c,s,η)的剩余t+1個(gè)特征值.定理1證畢.

例1設(shè)廣義核-衛(wèi)星圖Θ(c,s,η)=Θ(2,23,15)如圖1所示.

圖1 廣義核-衛(wèi)星圖Θ(2,23,15)

由定理1可得其無符號(hào)拉普拉斯譜特征值為：

2)λ=s1+c-2=3,其重?cái)?shù)為η1(s1-1)=4,λ=s2+c-2=5,其重?cái)?shù)為η2(s2-1)=4;

3)λ=2s1+c-2=6,其重?cái)?shù)為η1-1=1;

λ3-29λ2+246λ-600=0?

λ1=15.905 0,λ2=8.815 9,λ3=4.279 1.

通過Matlab直接計(jì)算，可得Θ(2,23,15)的無符號(hào)拉普拉斯譜為{11,3(4),5(4),6,15.905 0,8.815 9,4.279 1}，進(jìn)一步驗(yàn)證定理1成立.

在定理1中令t=1,可得核-衛(wèi)星圖Θ(c,s,η)的無符號(hào)拉普拉斯譜.

定理2核-衛(wèi)星圖Θ(c,s,η)的無符號(hào)拉普拉斯譜由下列特征值構(gòu)成：

1)特征值λ=c+ηs-2，其重?cái)?shù)為c-1；

2)特征值λ=s+c-2，其重?cái)?shù)為η(s-1)；

3)特征值λ=2(s-1)+c，其重?cái)?shù)為η-1；

4)余下2個(gè)特征值為

例2設(shè)核-衛(wèi)星圖Θ(2,2,3)如圖2所示.

圖2 核-衛(wèi)星圖Θ(2,2,3)

由定理2可得其無符號(hào)拉普拉斯特征值為：

1)λ=c-2+ηs=6,其重?cái)?shù)為c-1=1;

2)λ=s+c-2=2,其重?cái)?shù)為η(s-1)=3(2-1)=3;

3)λ=2(s-1)+c=2(2-1)+2=4,其重?cái)?shù)為η-1=3-1=2;

用Matlab直接計(jì)算可得Θ(2,2,3)的無符號(hào)拉普拉斯譜為{2(4),4(2),6,10}，進(jìn)一步驗(yàn)證定理2成立.

在定理2中,若令c=m,s=1,η=n,則

m(n-1); (n+m-2)(m-2).

其中，a(b)表示a重復(fù)b次.

眾所周知，整譜圖的構(gòu)造是圖譜理論研究的重要課題，文獻(xiàn)[7]研究了正則圖的連圖的無符號(hào)拉普拉斯譜，并構(gòu)造了一些無符號(hào)拉普拉斯整譜圖.直接利用定理2,可得核-衛(wèi)星圖Θ(c,s,η)是無符號(hào)拉普拉斯整譜圖的充分必要條件,該結(jié)果推廣了文獻(xiàn)[7]中的主要結(jié)果.

定理3核-衛(wèi)星圖Θ(c,s,η)是無符號(hào)拉普拉斯整譜圖的充分必要條件是

(ηs+c-2s)2+4scη∈Z2.

證明 定理2表明核-衛(wèi)星圖Θ(c,s,η)是無符號(hào)拉普拉斯整譜圖當(dāng)且僅當(dāng)

是整數(shù).由于ηs+3c+2s-4與(ηs+c-2s)2+4csη有相同的奇偶性,故λ±是整數(shù)當(dāng)且僅當(dāng)

(ηs+c-2s)2+4scη∈Z2.

定理3證畢.

直接應(yīng)用定理3,可得:

在定理1中,若令t=2,η1=η2=1,即廣義核-衛(wèi)星圖僅含有2個(gè)不同的星團(tuán)，則

推論3[7]廣義核-衛(wèi)星圖Θ(c,s,η)?Kc(Ks1∪Ks2)是無符號(hào)拉普拉斯整譜圖的充分必要條件是(c+2s1+2s2)2-16s1s2∈Z2.

證明 由定理1知,Kc(Ks1∪Ks2)是無符號(hào)拉普拉斯整譜圖當(dāng)且僅當(dāng)三次方程

(λ-2c-s1-s2+2)(λ-2s1-c+2)×

(λ-2s2-c+2)=

c(s1(λ-2s2-c+2)+s2(λ-2s1-c+2))

的根是整數(shù).根據(jù)三次方程的求根公式,類似于定理3的證明可得結(jié)論成立.推論3證畢.

推論4[7]對于n∈Z+,1≤j<2n，圖Kj(K2n-j∪Kn)是無符號(hào)拉普拉斯整譜圖.特別地，圖Kn(Kn+2∪Kn+1),Kn+2(Kn∪Kn+1),K1(K2n-1∪Kn)和K2n-1(K1∪Kn)也都是無符號(hào)拉普拉斯整譜圖.

2 結(jié) 語

本文刻畫了廣義核-衛(wèi)星圖的無符號(hào)拉普拉斯譜,應(yīng)用所得結(jié)果給出了幾類圖是無符號(hào)拉普拉斯整譜圖的充要條件.由于廣義核-衛(wèi)星圖是一種特殊的連圖,因此本文結(jié)果進(jìn)一步表明,圖的運(yùn)算(如連運(yùn)算、冠運(yùn)算、積運(yùn)算等)是構(gòu)造無符號(hào)拉普拉斯整譜圖的有效方法.另外, 廣義核-衛(wèi)星圖是現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)模型之一,有著廣泛的應(yīng)用背景.顯然, 對于復(fù)雜網(wǎng)絡(luò)中的其他模型,也可以考慮刻畫其無符號(hào)拉普拉斯譜及相關(guān)問題.