Indu-Bala乘積圖的廣義距離譜

盧鵬麗，劉文智

(蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050)

距離譜理論[1]作為圖論的一個重要研究方向，主要是通過圖的各類矩陣(距離矩陣、距離拉普拉斯矩陣等)、特征根及其特征向量來研究圖的拓撲結(jié)構(gòu)和代數(shù)性質(zhì)，廣泛應用于計算機、復雜系統(tǒng)、化學、物理等學科中。關(guān)于距離譜和距離(無符號)拉普拉斯譜的研究現(xiàn)狀如下：學者們已經(jīng)計算得到了圈圖[2]、路圖[3]和完全二部圖[4]等簡單圖的距離譜；Stevanovic和Indulal[5-6]得到了正則圖的聯(lián)圖的距離譜，距離正則圖和完全圖的簇圖的距離譜；Barik和Sahoo[7]得到了距離正則圖和正則圖的冠圖的距離譜和距離(無符號)拉普拉斯譜；其他研究成果見文獻[8-11]。在此基礎上，本文計算了一類組合圖的廣義距離譜。通過簡單地參數(shù)賦值，就可以得到距離(無符號)拉普拉斯譜，大大減少了距離矩陣相關(guān)譜的計算量。

1 基本概念和引理

2013年，Aouchiche和Hansen[1]受拉普拉斯矩陣和無符號拉普拉斯矩陣的啟發(fā)，提出了圖的距離拉普拉斯矩陣和距離無符號拉普拉斯矩陣的概念，并研究它們的譜。圖G的傳遞矩陣記為Tr(G)，是對角線元素為Tr(vi)的n×n維對角矩陣。圖G的距離拉普拉斯矩陣和距離無符號拉普拉斯矩陣分別記為L(G)=Tr(G)-D(G)和Q(G)=Tr(G)+D(G)，相應的特征值分別為λ1L(G)≥λ2L(G)≥…≥λnL(G)=0，λ1Q(G)≥λ2Q(G)≥…≥λnQ(G)，相應的特征值及其重數(shù)所構(gòu)成的集合稱為圖G的距離拉普拉斯譜和距離無符號拉普拉斯譜，記為L-譜和Q-譜。

受到Ligong Wang[12]和G. Indulal[13]論文的啟發(fā)。文獻[12]中，圖Kn,n+1≡Kn+1,n是將Kn,n+1復制2次，然后將2個復制圖中的n+1個對應頂點相連接，其中Kn,n+1是完全二部圖，作者證明了Kn,n+1≡Kn+1,n是鄰接整譜圖。文獻[13]中，作者將圖Kn,n+1≡Kn+1,n一般化到圖G1G2，是將G1和G2的聯(lián)圖復制2次，然后將2個復制圖中G2的對應頂點相連接所得到的圖，計算了其距離譜。明顯地，圖Kn,n+1≡Kn+1,n是圖G1G2的一種特殊圖在此基礎上計算了G1G2的廣義距離譜，進而求得距離(無符號)拉普拉斯譜。

引理1[15]設圖G的距離拉普拉斯譜為{λ1L(G)≥λ2L(G)≥…≥λnL(G)=0}，平均傳遞為t(G)，則圖G的距離拉普拉斯譜能量定義為:

引理2[15]設圖G的距離無符號拉普拉斯譜為{λ1Q(G)≥λ2Q(G)≥…≥λnQ(G)}，平均傳遞為t(G)，則圖G的距離無符號拉普拉斯譜能量定義為:

2 圖G1G2的廣義距離譜

定理1設圖Gi是有ni個頂點的ri-正則圖，其鄰接矩陣Ai對應的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的廣義距離譜為:

1)(5n1+3n2-r1+λ1j)α-λ1j-2，j=2,3,…,n1,每一個重數(shù)為2；

2)(3n1+5n2-2r2+2λ2j)α-2λ2j-4，j=2,3,…,n2；

3)(3n1+5n2-2r2-4)α，重數(shù)為n2-1；

4)方程組的解

其中，B*=(3n1+3n2)α+2n1-r1-2，C*=(3n1+3n2-r2-2)α+2n2-r2-2。

證明：對圖G1G2的頂點進行適當編號，圖G1G2的距離矩陣可以表示為:

根據(jù)距離矩陣，得到圖G1G2中每個頂點的傳遞Tr(u)=5n1+3n2-r1-2，u∈V(G1)；Tr(v)=3n1+5n2-2r2-4，v∈V(G2)。因此，圖G1G2的廣義距離矩陣可以表示為:

式中：M*=(3n1+5n2-2r2-4)αI+(1-α)(2J-2I-A2);N*=(5n1+3n2-r1-2)αI+(1-α)(2J-2I-A1);J是全1矩陣;I是單位矩陣。

因為Gi是ri-正則圖，所以Ai的特征值ri所對應的特征向量是全1向量1，其他特征向量都和1正交。設Ai的特征值λi≠ri所對應的特征向量為Xi，則AiXi=λiXi，1TXi=0，i=1,2。

求解方程組可得：

μ=(3n1+5n2-2r2+2λ2j)α-2λ2j-4，j=2,3,…,n2；μ=(3n1+5n2-2r2-4)α，重數(shù)為n2-1。

設σ是矩陣Dα(G1G2)的特征向量φ所對應的特征值，根據(jù)Dα(G1G2)φ=σφ和Ai1=ri1，i=1,2可得:

式中:B*=(3n1+3n2)α+2n1-r1-2，C*=(3n1+3n2-r2-2)α+2n2-r2-2。

假設β=0代入上面方程組，化簡得γ=δ=ε=0，矛盾。因此，不失一般性，假設α=1求解上面方程組可得定理中的第(4)部分，證畢。

3 圖G1G2的距離拉普拉斯譜

定理2設圖Gi是有ni個頂點的ri-正則圖，其鄰接矩陣Ai對應的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的距離拉普拉斯譜為:

1)5n1+3n2-r1+λ1j，j=2,3,…,n1,每一個重數(shù)為2；

2)3n1+5n2-2r2+2λ2j，j=2,3,…,n2；

3)3n1+5n2-2r2-4，重數(shù)為n2-1；

證明：已知Dα(G)-Dβ(G)=(α-β)L(G)，取α=1，β=0得L(G1G2)=D1(G1G2)-D0(G1G2)，則由定理1可得定理2，證畢。

4 圖G1G2的距離無符號拉普拉斯譜

定理3設圖Gi是有ni個頂點的ri-正則圖，其鄰接矩陣Ai對應的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的距離無符號拉普拉斯譜為:

1)5n1+3n2-r1-λ1j-4，j=2,3,…,n1, 每一個重數(shù)為2；

2)3n1+5n2-2r2-2λ2j-8，j=2,3,…,n2；

3)3n1+5n2-2r2-4，重數(shù)為n2-1；

5 結(jié)論

1)主要研究了2個正則圖經(jīng)過Indu-Bala乘積這一圖操作之后所形成的合成圖的廣義距離譜，揭示了合成圖的廣義距離譜、距離(無符號)拉普拉斯譜與原圖的鄰接譜之間的關(guān)系，不僅拓寬了組合圖廣義距離譜的研究范圍，而且大大減少了距離(無符號)拉普拉斯譜的計算量；

2)得到了一類特殊的距離(無符號)拉普拉斯整譜圖；

3)得到了特殊圖的距離(無符號)拉普拉斯譜能量公式。