盧鵬麗, 劉曉剛
(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院,甘肅 蘭州 730050; 2.墨爾本大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,澳大利亞 墨爾本 3010)
?
似雙星樹(shù)H(p,n,q)由Laplacian譜刻畫(huà)
盧鵬麗1, 劉曉剛2
(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院,甘肅 蘭州 730050; 2.墨爾本大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,澳大利亞 墨爾本 3010)
摘要:似雙星樹(shù)是恰好有兩個(gè)結(jié)點(diǎn)的度大于2的樹(shù)。用H(p,n,q)表示將路圖Pn的兩個(gè)懸掛點(diǎn)分別與星圖S(1,p)及S(1,q)的中心點(diǎn)重合所得到的一類(lèi)似雙星樹(shù)。首先得到了頂點(diǎn)的度序列,然后由譜性質(zhì)證明了似雙星樹(shù)H(p,n,q)由Laplacian譜確定,擴(kuò)大了譜確定圖的范圍。
關(guān)鍵詞:鄰接譜;Laplacian譜;A-同譜圖;L-同譜圖;線(xiàn)圖

1基本引理
引理1[13-23]對(duì)任意圖,由它的鄰接譜或Laplacian譜可確定:
1) 結(jié)點(diǎn)的個(gè)數(shù);
2) 邊的條數(shù)。
對(duì)任意圖,由它的鄰接譜可確定:
3) 圖中任意長(zhǎng)度的閉回路的數(shù)目。
對(duì)任意圖,由它的Laplacian譜可確定:
4)圖的組成分支數(shù)目;
5)生成樹(shù)的個(gè)數(shù);
6)結(jié)點(diǎn)度的平方和。
引理2[24]對(duì)任意圖,長(zhǎng)度為4的閉回路的數(shù)目等于2倍的邊數(shù)加上4倍的長(zhǎng)度為2的導(dǎo)出路的數(shù)目,再加上8倍的長(zhǎng)度為4的圈圖的數(shù)目。
原圖G的線(xiàn)圖記為(G)。在線(xiàn)圖(G)中,其結(jié)點(diǎn)相當(dāng)于原圖G的邊,當(dāng)且僅當(dāng)原圖G中的兩條邊有公共結(jié)點(diǎn)時(shí),線(xiàn)圖(G)中的結(jié)點(diǎn)則為鄰接點(diǎn)。
引理3[25]設(shè)T是有n個(gè)結(jié)點(diǎn)的樹(shù),(T)是它的線(xiàn)圖,則有
式中:i=1,2,…,n-1。
引理4[26]設(shè)u是圖G的一個(gè)結(jié)點(diǎn),從圖G中去掉結(jié)點(diǎn)u及其結(jié)點(diǎn)u的關(guān)聯(lián)邊得到子圖G-u,有
引理5[2]設(shè)e是圖G的一條邊,從圖G中去掉邊e得到子圖G′=G-e,有

式中:i=1,2,…,m。
引理7[27-28]設(shè)圖G的結(jié)點(diǎn)集V(G)和邊集E(G)都不為空,有
式中:mi是圖G中所有與結(jié)點(diǎn)vi相鄰的結(jié)點(diǎn)的度的平均值。
引理 8[29]設(shè)圖G是結(jié)點(diǎn)數(shù)大于等于3的連通圖,則有……p>