李 佳 建

(蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州 730070)

近幾年，關(guān)于拉普拉斯譜的研究取得了一些新的成果。文獻(xiàn)[1]得到了H-聯(lián)圖的拉普拉斯特征多項(xiàng)式，給出了H-聯(lián)圖的拉普拉斯譜與圖G1、G2、…、Gk之間的關(guān)系。文獻(xiàn)[2]研究了一致超圖的拉普拉斯譜和正規(guī)拉普拉斯譜的一些性質(zhì)。文獻(xiàn)[3]刻畫了圖的字典積的任意冪的鄰接譜和拉普拉斯譜。文獻(xiàn)[4]利用因子圖的譜性質(zhì)，建立了直積圖和強(qiáng)積圖的拉普拉斯譜的估計(jì)方法。文獻(xiàn)[5]和文獻(xiàn)[6]討論了在圖的一些乘積運(yùn)算下拉普拉斯譜的性質(zhì)。此外，還有一些關(guān)于拉普拉斯譜的其他成果[7-12]。

1 基礎(chǔ)說明

本文考慮的圖都是無向的簡單圖。設(shè)圖G的頂點(diǎn)集V(G)={v1,v2,…,vn}，邊集E(G)={vivj|vi,vj∈V(G)}(vi與vj相鄰)。圖G的鄰接矩陣A(G)=(aij)n×n定義為：若vivj∈E(G)，則aij=1；否則aij=0。設(shè)λ1≥λ2≥…≥λn為圖G的鄰接矩陣A(G)的特征值(A(G)的特征值的多重集稱為圖G的譜，記為Spec(G))。設(shè)D(G)=diag(d1,d2,…,dn)為圖G的度對(duì)角陣，其中di表示頂點(diǎn)vi的度。圖G的拉普拉斯矩陣L(G)=D(G)-A(G)，其特征值為μ1≥μ2≥…≥μn=0(L(G)的特征值的多重集稱為圖G的拉普拉斯譜，記為SpecL(G))。

圖G與圖H的笛卡爾積，記為G□H，其頂點(diǎn)集為V(G)×V(H)={(a,v):a∈V(G),v∈V(H)}，頂點(diǎn)(a,v)與(b,w)在G□H中相鄰，當(dāng)且僅當(dāng)a=b且vw∈E(H)，或v=w且ab∈E(G)。設(shè)G1i=G1，G2i=G2分別為圖G1與圖G2的k次復(fù)制(1≤i≤k),Gj(j=3,4)為k階圖。2018年，文獻(xiàn)[13]首次引入了兩種新運(yùn)算：第一種運(yùn)算G1■k(G3□G2)是指首先將G3與G2做笛卡爾積，從而產(chǎn)生G2的k次復(fù)制G2i，然后將G1i與G2i做聯(lián)運(yùn)算G1i∨G2i(i=1,2,…,k)。例如，當(dāng)圖G1=G2=K2、G3=P3時(shí)，G1■k(G3□G2)如圖1所示；第二種運(yùn)算(G4□G1)■k(G3□G2)是指首先將G4與G1做笛卡爾積，從而產(chǎn)生G1的k次復(fù)制G1i，同時(shí)將G3與G2做笛卡爾積，從而產(chǎn)生G2的k次復(fù)制G2i，然后將G1i與G2i做聯(lián)運(yùn)算G1i∨G2i(i=1,2,…,k)。例如，當(dāng)圖G1=G2=K2、G3=G4=P3時(shí)，(G4□G1)■k(G3□G2)如圖2所示。受此啟發(fā)，本文討論這兩類圖的拉普拉斯譜。

2 主要結(jié)果

引理1[14]設(shè)G1和G2分別為n1和n2階圖，A1和A2分別為G1和G2的鄰接矩陣，則G1□G2的鄰接矩陣A1□A2=A1?In2+In1?A2。

引理2[15]設(shè)u和v分別為圖G1和圖G2的屬于特征值(或拉普拉斯特征值)θ和η的特征向量。則向量w=u?v(ω(x,y)=uxvy)是G1□G2的屬于特征值(或拉普拉斯特征值)θ+η的特征向量。

下面給出本文的主要結(jié)論。先來刻畫圖G1■k(G3□G2)的拉普拉斯譜。

證明:令J為元素全為1的矩陣。對(duì)頂點(diǎn)進(jìn)行適當(dāng)排列，由引理1可得G1■k(G3□G2)的拉普拉斯矩陣

為L(G)的屬于特征值n1+r2-λ2,i+μ3,j的特征向量。

[a111×n1,a211×n1,…,ak11×n1,b111×n2,b211×n2,…,bk11×n2]Τ=[a′?11×n1,b′?11×n2]Τ。

其中a′=[a1,a2,…,ak],b′=[b1,b2,…,bk],[a1,a2,…,ak,b1,b2,…,bk]≠01×2k。

L(G)[a′?11×n1,b′?11×n2]Τ=ν[a′?11×n1,b′?11×n2]Τ。

那么，可得到如下含有2k個(gè)方程的方程組：

下面討論矩陣H1的特征值。為此僅需考慮det(νI2k-H1)=0的根。如果ν=n2，由式(1)有bin2=0。但n2>0，從而bi=0。進(jìn)一步由式(2)可知ai=0。與[a1,a2,…,ak,b1,b2,…,bk]≠01×2k矛盾，從而ν≠n2。故(ν-n2)Ik是非奇異的，即|(ν-n2)Ik|≠0。

注意到

接下來，刻畫圖(G4□G1)■k(G3□G2)的拉普拉斯譜。

證明:令J為元素全為1的矩陣。對(duì)頂點(diǎn)進(jìn)行適當(dāng)排列，可得(G4□G1)■k(G3□G2)的拉普拉斯矩陣

[a111×n1,a211×n1,…,ak11×n1,b111×n2,b211×n2,…,bk11×n2]Τ=[a′?11×n1,b′?11×n2]Τ。

其中a′=[a1,a2,…,ak],b′=[b1,b2,…,bk],[a1,a2,…,ak,b1,b2,…,bk]≠01×2k。

L(G)[a′?11×n1,b′?11×n2]Τ=ν[a′?11×n1,b′?11×n2]Τ。

那么我們可得到如下含有2k個(gè)方程的方程組

(3)

若在定理2中限制G3與G4是兩個(gè)同構(gòu)的圖，則可得:

推論1 設(shè)圖Gi為ni階ri-正則圖，且其特征值為λi,1=ri≥λi,2≥…≥λi,ni(i=1,2)并設(shè)G3和G4是兩個(gè)同構(gòu)的k階圖，則(G3□G1)■k(G3□G2)的拉普拉斯譜是由數(shù)

和n1+r2-λ2,i+μ3,j(i=2,…,n2;j=1,…,k)組成的多重集。這里μ3，j(j=1,…,k)是圖G3的拉普拉斯特征值。

故矩陣H2與H2′相似，從而

|νI2k-H2|

=|νI2k-H2′|

由此得出矩陣H2的2k個(gè)特征值為

最后，給出主要結(jié)果的兩個(gè)應(yīng)用實(shí)例。

例1 設(shè)Gi=K2(i=1,2)，G3=P3，則圖K2■3(P3□K2)如圖1所示。注意到n1=n2=2，r1=r2=1，圖G1、G2的鄰接矩陣A(K2)的特征值為λ1,2=λ2,2=-1，圖G3的拉普拉斯矩陣L(P3)的特征值分別為μ3,1=0、μ3,2=1、μ3,3=3。由定理1立得圖K2■3(P3□K2)的拉普拉斯譜:

SpecL(K2■3(P3□

例2 設(shè)Gi=K2(i=1,2)，Gj=P3(j=3,4)，則圖(P3□K2)■3(P3□K2)如圖2所示。同理，注意到n1=n2=2，r1=r2=1，λ1,2=λ2,2=-1，μ3,1=0,μ3,2=1,μ3,3=3。由定理2 和推論1可得圖(P3□K2)■3(P3□K2)的拉普拉斯譜:

圖1 K2■3(P3□K2) 圖2 (P3□K2)■3(P3□K2)

3 結(jié) 語

一些“簡單”的圖類在一些圖的二元運(yùn)算作用后可得“復(fù)雜”的新圖，通過原圖的性質(zhì)刻畫新圖的相應(yīng)性質(zhì)是圖譜理論中的重要方法之一。本文針對(duì)基于圖的笛卡爾積和聯(lián)運(yùn)算所構(gòu)造的兩類新圖，給出了它們的拉普拉斯譜，并列舉了兩個(gè)應(yīng)用實(shí)例。文中所使用的方法對(duì)進(jìn)一步討論這兩類圖的無符號(hào)拉普拉斯譜或規(guī)范拉普拉斯譜仍有借鑒意義。