似雙星樹H(p,n,q)由Laplacian譜刻畫

盧鵬麗, 劉曉剛

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050; 2.墨爾本大學 數學與統計學院，澳大利亞 墨爾本 3010)

?

似雙星樹H(p,n,q)由Laplacian譜刻畫

盧鵬麗1, 劉曉剛2

(1.蘭州理工大學 計算機與通信學院，甘肅 蘭州 730050; 2.墨爾本大學 數學與統計學院，澳大利亞 墨爾本 3010)

摘要：似雙星樹是恰好有兩個結點的度大于2的樹。用H(p,n,q)表示將路圖Pn的兩個懸掛點分別與星圖S(1,p)及S(1,q)的中心點重合所得到的一類似雙星樹。首先得到了頂點的度序列，然后由譜性質證明了似雙星樹H(p,n,q)由Laplacian譜確定，擴大了譜確定圖的范圍。

關鍵詞：鄰接譜；Laplacian譜；A-同譜圖；L-同譜圖；線圖

1基本引理

引理1[13-23]對任意圖，由它的鄰接譜或Laplacian譜可確定：

1) 結點的個數；

2) 邊的條數。

對任意圖，由它的鄰接譜可確定：

3) 圖中任意長度的閉回路的數目。

對任意圖，由它的Laplacian譜可確定：

4)圖的組成分支數目；

5)生成樹的個數；

6)結點度的平方和。

引理2[24]對任意圖，長度為4的閉回路的數目等于2倍的邊數加上4倍的長度為2的導出路的數目，再加上8倍的長度為4的圈圖的數目。

原圖G的線圖記為(G)。在線圖(G)中，其結點相當于原圖G的邊，當且僅當原圖G中的兩條邊有公共結點時，線圖(G)中的結點則為鄰接點。

引理3[25]設T是有n個結點的樹，(T)是它的線圖，則有

式中：i=1,2,…,n-1。

引理4[26]設u是圖G的一個結點，從圖G中去掉結點u及其結點u的關聯邊得到子圖G-u，有

引理5[2]設e是圖G的一條邊，從圖G中去掉邊e得到子圖G′=G-e，有

式中：i=1,2,…,m。

引理7[27-28]設圖G的結點集V(G)和邊集E(G)都不為空，有

式中：mi是圖G中所有與結點vi相鄰的結點的度的平均值。

引理 8[29]設圖G是結點數大于等于3的連通圖，則有