兩類交叉四角鏈的拉普拉斯譜及其應(yīng)用

涂淑玲，王廣富

（華東交通大學(xué)理學(xué)院，江西 南昌 330013）

在圖論中， 拉普拉斯矩陣是圖的一種矩陣表示，定義為圖的度矩陣與鄰接矩陣的差。 拉普拉斯矩陣的所有特征值稱為圖的拉普拉斯譜。 拉普拉斯譜及其應(yīng)用可以解決復(fù)雜網(wǎng)絡(luò)中的許多理論問(wèn)題[1-2]，網(wǎng)絡(luò)的拉普拉斯譜的計(jì)算在拓?fù)浣Y(jié)構(gòu)和動(dòng)力學(xué)等方面有諸多應(yīng)用。 例如，在化學(xué)上，對(duì)于用來(lái)反映化合物分子結(jié)構(gòu)的基爾霍夫指標(biāo)已有 廣 泛的研 究。 1993 年，Klein 等[3]提 出 了 一 個(gè) 新的距離函數(shù)——電阻距離。 圖的每條邊等價(jià)于一個(gè)單位電阻，然后利用歐姆定律計(jì)算出任意兩個(gè)頂點(diǎn)之間的有效電阻，即電阻距離；圖中所有頂點(diǎn)對(duì)之間的電阻距離之和定義為圖的基爾霍夫指標(biāo)。 網(wǎng)絡(luò)的基爾霍夫指標(biāo)可以用非零拉普拉斯特征值的倒數(shù)之和來(lái)表示[4]；網(wǎng)絡(luò)的生成樹(shù)數(shù)目可以由所有非零拉普拉斯特征值的乘積來(lái)確定[5]；網(wǎng)絡(luò)的直徑可以由拉普拉斯矩陣的第二小特征值來(lái)估算[6]。 盡管從分析的角度，拉普拉斯譜的計(jì)算只是一個(gè)理論上的挑戰(zhàn)，但建立網(wǎng)絡(luò)的拉普拉斯譜是很有意義的。 近二十年來(lái)，有很多人在研究各類分子圖的拉普拉斯譜的計(jì)算及其應(yīng)用[3，4，7-11]。 Yang等[12]研究了線性六角鏈的部分拉普拉斯特征值，從而確定了其基爾霍夫指標(biāo)。 之后， 人們通過(guò)Yang 等[12]的方法得到了其他一些分子網(wǎng)絡(luò)的部分拉普拉斯特征值及基爾霍夫指標(biāo)，如苯環(huán)[13]、五邊形鏈[14]等。 Pan 等[15]研究了線性交叉多聯(lián)骨牌鏈（即線性交叉四角鏈) 的部分拉普拉斯特征值、基爾霍夫指標(biāo)及生成樹(shù)數(shù)目。 直接計(jì)算出某圖類的所有的拉普拉斯特征值還是很困難的。 本文主要研究并確定了線性交叉四角鏈和交叉四角柱狀鏈兩類圖的拉普拉斯譜，更簡(jiǎn)便地得到了這兩類圖的基爾霍夫指標(biāo)及其生成樹(shù)數(shù)目表達(dá)式。 另外，還利用交叉四角柱狀鏈的拉普拉斯譜，推導(dǎo)出交叉四角柱狀鏈的度-基爾霍夫指標(biāo)的表達(dá)式。

1 預(yù)備知識(shí)

本文考慮的均為連通無(wú)向圖，即圖中任意兩個(gè)頂點(diǎn)都存在路徑使其連通。 設(shè)圖G=（V，E），V＝｛1，2，…，n｝和E＝｛e1，e2，…，em｝分別為圖G 的頂點(diǎn)集和邊集。 di表示頂點(diǎn)i 的度，i＝1，2，…，n。 文中未加說(shuō)明的符號(hào)以及定義等參見(jiàn)文獻(xiàn)[16]。

定義1.1 圖的拉普拉斯矩陣是指由頂點(diǎn)集V作為行和列進(jìn)行索引n×n 的矩陣，記為L(zhǎng)（G）=（lij），其中

定義1.2 拉普拉斯矩陣L（G）的所有特征值稱為圖G 的拉普拉斯譜；若L（G）的特征值為λ1≥λ2≥…≥λn-1＞λn=0， 那么圖G 的拉普拉斯譜可記為S（G）=（λ1，λ2，…，λn）。

定義1.3 設(shè)H1＝（V1，E1），H2＝（V2，E2）是兩個(gè)頂點(diǎn)集不相交的簡(jiǎn)單圖，對(duì)頂點(diǎn)集V＝V1×V2（即V1與V2的卡氏積） 中的任意兩個(gè)點(diǎn)u=（ui，vj） 和v=（up，vq），當(dāng)ui與up相鄰或者ui=up且vj與vq相鄰時(shí)就將u 和v 連一條邊所得到的圖。 稱之為H1與H2的合成圖，記為H=H1[H2]。

定義1.4 圖G 的一個(gè)生成子圖若是一棵樹(shù)，稱為圖G 的一棵生成樹(shù)。

定義1.5 將圖G 看成一個(gè)電網(wǎng)絡(luò)N 且圖G的每條邊等價(jià)于一個(gè)單位電阻，然后計(jì)算出電網(wǎng)絡(luò)N 中任意兩個(gè)頂點(diǎn)i 與j 之間的有效電阻，即頂點(diǎn)i與j 之間的電阻距離，記為rij[3]。

Hou 等[19]得到了任意兩個(gè)圖的合成圖的拉普拉斯特征值和生成樹(shù)數(shù)目的表達(dá)式，其中結(jié)構(gòu)相同而標(biāo)號(hào)不同的生成樹(shù)視為不同的生成樹(shù)。

引理1.9 設(shè)H=H1[H2]，其中｜V（H1）｜＝s，｜V（H2）｜＝t，若S（H1）=（0，μ1，…，μs-1），S（H2）=（0，ω1，…，ωt-1）,圖H1的度序列記為d（H1）=（d1，d2，…，ds），那么H=H1[H2]的拉普拉斯特征值是0，tμi（i=1，…，s-1），tdl+ωj（l=1，…，s；j=1，…，t-1）[19]。

引理1.10 設(shè)H=H1[H2]，那么的生成樹(shù)數(shù)目τ（H1[H2]）的值為[19]

如圖1 所示， 設(shè)Xn是由n 個(gè)完全圖K4構(gòu)成且經(jīng)過(guò)適當(dāng)標(biāo)號(hào)的一條線性交叉四角鏈；Gn是由n 個(gè)完全圖K4組成的交叉四角柱狀鏈， 其平面展開(kāi)圖如圖2（a）所示，G6的立體圖如圖2（b）所示。

圖1 線性交叉四角鏈XnFig.1 Linear crossed polyomino chain Xn

圖2 交叉四角柱狀鏈Fig.2 Crossed polyomino cylinder chain

可以發(fā)現(xiàn)：Xn可看成是一條路與K2的合成圖，即Xn=Pn+1[K2]，其中Pn+1表示一條n+1 個(gè)頂點(diǎn)的路；Gn是具有n 個(gè)頂點(diǎn)的圈Cn與K2的合成圖， 即Gn=Cn[K2]。

2 線性交叉四角鏈Xn 的拉普拉斯譜及其應(yīng)用

下面是Xn的拉普拉斯譜的兩個(gè)應(yīng)用。

2.1 Xn 的基爾霍夫指標(biāo)

定理1 設(shè)Xn為線性交叉四角鏈，則

2.2 Xn 的生成樹(shù)數(shù)目

定理2 若用τ（Xn）表示線性交叉四角鏈Xn生成樹(shù)的數(shù)目，則

定理得證。

實(shí)例驗(yàn)證：當(dāng)n=1 時(shí)，交叉四角鏈X1即為K4,

故，結(jié)論成立。

圖3 X1Fig.3 X1

下面計(jì)算出了線性交叉四角鏈從X1到X50的基爾霍夫指標(biāo)，如表1 所示，從X1到X20的生成樹(shù)的數(shù)目如表2 所示。

表1 線性交叉四角鏈從X1 到X50 的基爾霍夫指標(biāo)Tab.1 Kirchhoff indices of linear crossed polyomino chain from X1 to X50

3 交叉四角柱狀鏈Gn 的拉普拉斯譜及其應(yīng)用

與上一部分相同， 先利用引理1.9 計(jì)算Gn的拉普拉斯譜。

3.1 Gn 的基爾霍夫指標(biāo)

結(jié)合定理1 和定理3，得到以下推論：

推論 設(shè)Xn和Gn分別為線性交叉四角鏈和交叉四角柱狀鏈，則

3.2 Gn 的生成樹(shù)數(shù)目

定理4 設(shè)τ（Gn）為交叉四角柱狀鏈Gn生成樹(shù)的數(shù)目，則

證明：由于Gn的生成樹(shù)數(shù)目為n，根據(jù)引理1.10，

3.3 Gn 的度-基爾霍夫指標(biāo)

圖4 G1Fig.4 G1

結(jié)論得證。

下面也列出了交叉四角柱狀鏈從G1到G50的基爾霍夫指標(biāo)及從G1到G20的生成樹(shù)的數(shù)目，分別如表3 和表4 所示。

表3 交叉四角柱狀鏈從G1 到G50 的基爾霍夫指標(biāo)Tab.3 Kirchhoff indices of crossed polyomino cylinder chain from G1 to G50

表4 交叉四角柱狀鏈從G1 到G20 的生成樹(shù)的數(shù)目Tab.4 The number of spanning trees of crossed polyomino cylinder chain from G1 to G20

4 結(jié)論

1） 本文利用圖的合成運(yùn)算，得到了線性交叉四角鏈Xn和交叉四角柱狀鏈Gn的拉普拉斯譜。

2） 通過(guò)應(yīng)用拉普拉斯譜，得到了這兩類交叉四角鏈的基爾霍夫指標(biāo)、生成樹(shù)數(shù)目的表達(dá)式。

3） 利用正則性得到了交叉四角柱狀鏈的度-基爾霍夫指標(biāo)的表達(dá)式。

4） 這些表達(dá)式對(duì)這兩類圖的拓?fù)湫再|(zhì)提供了更深入的理解。