正則圖字典積的任意冪的無符號和正規(guī)拉普拉斯譜

魏 斌， 王維忠

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

通過對一些簡單的圖施加圖的運算往往會得到一些較復(fù)雜的圖。利用參與運算的因子圖的參數(shù)性質(zhì)，刻畫運算后得到新圖的相應(yīng)性質(zhì)，是圖論中的一種重要方法。2013年，WANG Wei-zhong等[1]給出了正則圖經(jīng)過兩種圖的一元運算后所得新圖的拉普拉斯特征多項式。文獻(xiàn)[2]和[3]對廣義聯(lián)圖分別刻畫了鄰接譜與拉普拉斯譜和特征多項式。2014年，WU Bao-feng等[4]刻畫了H-聯(lián)圖的無符號拉普拉斯譜和正規(guī)拉普拉斯譜。2017年，Abreu等[5]給出了字典積的任意冪的鄰接譜和拉普拉斯譜。受上述文獻(xiàn)的啟發(fā)，本文進(jìn)一步考慮當(dāng)G和H是正則圖時，Hk[G]的無符號拉普拉斯譜和正規(guī)拉普拉斯譜。

圖1 K2和H1[G]=C4[K2] 圖

1 預(yù)備知識

首先引入一些記號。設(shè)方陣M的無符號拉普拉斯譜和正規(guī)拉普拉斯譜分別為SpecQ(M)和SpecL(M)。符號a+SpecQ(M)(a+SpecL(M))表示對SpecQ(M)(SpecL(M))中的每個特征值加a；類似地，a·SpecQ(M)(a·SpecL(M))表示對SpecQ(M)(SpecL(M))中的每個特征值乘以a；而符號(SpecQ(M))[n]((SpecL(M)[n])表示對SpecQ(M)(SpecL(M))中的每個特征值的重數(shù)乘以n。文中的其他記號和術(shù)語參見文獻(xiàn)[7-9]。

接下來，給出幾個引理。

引理2[4]設(shè)H和G分別是階數(shù)為n和m的正則連通圖，正則度分別為q和p。則

SpecQ(H[G])=(mq+(SpecQ(G){2p}))[n]∪(2p+mSpecQ(H))。

引理3[4]設(shè)H和G分別是階數(shù)為n和m的正則連通圖，正則度分別為q和p。則

2 主要結(jié)果

在這一部分，將給出正則圖的字典積的任意冪的無符號拉普拉斯譜和正規(guī)拉普拉斯譜。在以下敘述中采用集合并集的傳統(tǒng)表示方法來表示多重集的并集，即集合A和集合B中的公共元素在A∪B中出現(xiàn)的次數(shù)等于在A和B中出現(xiàn)的次數(shù)之和。

2.1 無符號拉普拉斯譜

首先刻畫Hk[G](k≥0)的無符號拉普拉斯譜。

定理1 設(shè)H和G分別是階數(shù)為n和m的正則連通圖，正則度分別為q和p。則

SpecQ(Hk[G])=(A∪B∪C)D，

其中

C=(2rk-1+mnk-1SpecQ(H))，

注1 當(dāng)k=0時，SpecQ(H0[G])=SpecQ(G)。

證明下面按迭代次數(shù)k進(jìn)行歸納證明。

(ⅰ) 當(dāng)k=1時，注意到B=?，由引理2知結(jié)論顯然成立。

(ⅱ) 假定迭代次數(shù)等于k-1時命題依然成立，即

SpecQ(Hk-1[G])=(A1∪B1∪C1)D1，

其中

C1=(2rk-2+mnk-2SpecQ(H))，

則當(dāng)?shù)螖?shù)為k時，由Hk[G]的定義及引理2可知

SpecQ(Hk[G])=SpecQ(H[Hk-1[G]])=

(mnk-1q+(SpecQ(Hk-1[G])2rk-1))[n]∪(2rk-1+mnk-1SpecQ(H))，

將SpecQ(Hk-1[G])=(A1∪B1∪C1)D1代入上式可得

(A∪B∪C)D，

從而當(dāng)?shù)螖?shù)等于k時，命題依然成立。定理得證。

下面的推論1給出一個正則圖與它自身的字典積的任意冪的無符號拉普拉斯譜。事實上，設(shè)H是連通的正則圖，且H0=K1(孤立點)，H1=H，Hk=Hk-1[H](k≥2)。則由定理1立得如下推論。

推論1 設(shè)H是n階q-正則連通圖，則Hk的無符號拉普拉斯譜為

SpecQ(Hk)=(A∪B∪C)D，

其中

C=(2rk-1+nk-1SpecQ(H))，

下面給出定理1的一個簡單應(yīng)用。

例1 如圖1所示，m=2,n=4,p=1,q=2，則由定理1可知

其中

C=(2rk-1+2×4k-1SpecQ(H))，

特別地，當(dāng)k=2(如圖2所示)時，有

(10,18[4],20[16],22[8],26[2],42)。

2.2 正規(guī)拉普拉斯譜

接下來給出Hk[G]的正規(guī)拉普拉斯譜。

定理2 設(shè)H和G分別是階數(shù)為n和m的正則連通圖，正則度分別為q和p。則

其中

注2 當(dāng)k=0時，SpecL(H0[G])=SpecL(G)。

證明下面仍按迭代次數(shù)k進(jìn)行歸納證明。

(ⅰ) 當(dāng)k=1時，由引理3知結(jié)論顯然成立。

(ⅱ) 假定迭代次數(shù)等于k-1時命題成立，即

其中

則當(dāng)?shù)螖?shù)為k時，由Hk[G]的定義及引理3可知

SpecL(Hk[G])=SpecL(H[Hk-1[G]])=

從而當(dāng)?shù)螖?shù)等于k時命題依然成立。定理得證。

下面給出一個正則圖與它自身的字典積的任意冪的正規(guī)拉普拉斯譜。事實上，設(shè)H是一個正則圖，且H0=K1(孤立點)，H1=H，Hk=Hk-1[H](k≥2)。則由定理2立得如下推論。

推論2 設(shè)H是n階q-正則連通圖，則

其中

下面給出定理2的一個應(yīng)用例子。

例2 如圖1所示，m=2，n=4，p=1，q=2，則由定理2可知

其中

特別地，當(dāng)k=2(如圖2所示)時有

3 結(jié) 語