盧鵬麗，劉文智

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050)

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

1 基本概念和引理

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

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

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

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

2 圖G1G2的廣義距離譜

定理1設(shè)圖Gi是有ni個(gè)頂點(diǎn)的ri-正則圖，其鄰接矩陣Ai對(duì)應(yīng)的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的廣義距離譜為:

1)(5n1+3n2-r1+λ1j)α-λ1j-2，j=2,3,…,n1,每一個(gè)重?cái)?shù)為2；

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

3)(3n1+5n2-2r2-4)α，重?cái)?shù)為n2-1；

4)方程組的解

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

證明：對(duì)圖G1G2的頂點(diǎn)進(jìn)行適當(dāng)編號(hào)，圖G1G2的距離矩陣可以表示為:

根據(jù)距離矩陣，得到圖G1G2中每個(gè)頂點(diǎn)的傳遞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是單位矩陣。

因?yàn)镚i是ri-正則圖，所以Ai的特征值ri所對(duì)應(yīng)的特征向量是全1向量1，其他特征向量都和1正交。設(shè)Ai的特征值λi≠ri所對(duì)應(yīng)的特征向量為Xi，則AiXi=λiXi，1TXi=0，i=1,2。

求解方程組可得：

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

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

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

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

3 圖G1G2的距離拉普拉斯譜

定理2設(shè)圖Gi是有ni個(gè)頂點(diǎn)的ri-正則圖，其鄰接矩陣Ai對(duì)應(yīng)的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的距離拉普拉斯譜為:

1)5n1+3n2-r1+λ1j，j=2,3,…,n1,每一個(gè)重?cái)?shù)為2；

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

3)3n1+5n2-2r2-4，重?cái)?shù)為n2-1；

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

4 圖G1G2的距離無符號(hào)拉普拉斯譜

定理3設(shè)圖Gi是有ni個(gè)頂點(diǎn)的ri-正則圖，其鄰接矩陣Ai對(duì)應(yīng)的鄰接譜為{ri,λi2,λi3,…,λini}，i=1,2。那么圖G1G2的距離無符號(hào)拉普拉斯譜為:

1)5n1+3n2-r1-λ1j-4，j=2,3,…,n1, 每一個(gè)重?cái)?shù)為2；

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

3)3n1+5n2-2r2-4，重?cái)?shù)為n2-1；

5 結(jié)論

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

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

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