盧鵬麗, 劉曉剛
(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的連通圖,則有……p>