涂淑玲，王廣富

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

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

1 預(yù)備知識

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

定義1.1 圖的拉普拉斯矩陣是指由頂點集V作為行和列進行索引n×n 的矩陣，記為L（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）是兩個頂點集不相交的簡單圖，對頂點集V＝V1×V2（即V1與V2的卡氏積） 中的任意兩個點u=（ui，vj） 和v=（up，vq），當(dāng)ui與up相鄰或者ui=up且vj與vq相鄰時就將u 和v 連一條邊所得到的圖。 稱之為H1與H2的合成圖，記為H=H1[H2]。

定義1.4 圖G 的一個生成子圖若是一棵樹，稱為圖G 的一棵生成樹。

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

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

引理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ù)目τ（H1[H2]）的值為[19]

如圖1 所示， 設(shè)Xn是由n 個完全圖K4構(gòu)成且經(jīng)過適當(dāng)標(biāo)號的一條線性交叉四角鏈；Gn是由n 個完全圖K4組成的交叉四角柱狀鏈， 其平面展開圖如圖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 個頂點的路；Gn是具有n 個頂點的圈Cn與K2的合成圖， 即Gn=Cn[K2]。

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

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

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

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

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

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

定理得證。

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

故，結(jié)論成立。

圖3 X1Fig.3 X1

下面計算出了線性交叉四角鏈從X1到X50的基爾霍夫指標(biāo)，如表1 所示，從X1到X20的生成樹的數(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 計算Gn的拉普拉斯譜。

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

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

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

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

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

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

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

圖4 G1Fig.4 G1

結(jié)論得證。

下面也列出了交叉四角柱狀鏈從G1到G50的基爾霍夫指標(biāo)及從G1到G20的生成樹的數(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ù)目Tab.4 The number of spanning trees of crossed polyomino cylinder chain from G1 to G20

4 結(jié)論

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

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

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

4） 這些表達式對這兩類圖的拓撲性質(zhì)提供了更深入的理解。