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

盧鵬麗, 劉曉剛

(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的連通圖，則有