兩類圖的拉普拉斯譜

李 佳 建

(蘭州交通大學 數理學院，甘肅 蘭州 730070)

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

1 基礎說明

本文考慮的圖都是無向的簡單圖。設圖G的頂點集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。設λ1≥λ2≥…≥λn為圖G的鄰接矩陣A(G)的特征值(A(G)的特征值的多重集稱為圖G的譜，記為Spec(G))。設D(G)=diag(d1,d2,…,dn)為圖G的度對角陣，其中di表示頂點vi的度。圖G的拉普拉斯矩陣L(G)=D(G)-A(G)，其特征值為μ1≥μ2≥…≥μn=0(L(G)的特征值的多重集稱為圖G的拉普拉斯譜，記為SpecL(G))。

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

2 主要結果

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

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

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

證明:令J為元素全為1的矩陣。對頂點進行適當排列，由引理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個方程的方程組：

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

注意到

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

證明:令J為元素全為1的矩陣。對頂點進行適當排列，可得(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個方程的方程組

(3)

若在定理2中限制G3與G4是兩個同構的圖，則可得:

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

和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個特征值為

最后，給出主要結果的兩個應用實例。

例1 設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 設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 結 語

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