給定獨(dú)立數(shù)的樹的最大拉普拉斯譜半徑

嚴(yán)亞偉，葉淼林，蘆興庭

（安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽安慶246133）

設(shè)G是一個(gè)n階簡(jiǎn)單無(wú)向圖，記其頂點(diǎn)集為V={ v1,v2,…,vn}，邊集 E={e1,e2,???,em}。NG(v)為G中與v相鄰的點(diǎn)的集合，且記v的度數(shù)d(v ) = |NG(v ) |。G的任意子圖H，任意的v∈V(G)，記 NH(v)=NG(v)?V(H)，dH(v)=|NH(v)|。若dG(v)=1，則稱v是圖G的葉子。Y(G)表示G中所有葉子的集合，稱與葉子關(guān)聯(lián)的邊為懸掛邊，與葉子關(guān)聯(lián)的點(diǎn)為支撐點(diǎn)，用G-xy表示G刪去邊xy∈E(G)而得到的圖，用G+xy表示圖G增加邊xy?E(G)而獲得的圖。圖G的獨(dú)立數(shù)記為α(G)[1]，獨(dú)立數(shù)是α的n階樹的集合記為Tn,α。圖G的度矩陣記為D( G )=diag(d (v1),d(v2),???,d(vn)),其中d(vi)是頂點(diǎn)vi的度數(shù)，i=1,2,…,n。圖G的鄰接矩陣為A( G ) =(aij)n×n，如果 vivj∈E，則 aij=1；否則aij=0。圖G的拉普拉斯矩陣為L(zhǎng)(G)=D(G)-A( G )，L(G)的最大特征值稱為圖G的拉普拉斯譜半徑，記為μ(G)。圖G的無(wú)符號(hào)拉普拉斯矩陣為Q( G ) =D( G ) +A( G )，Q(G)的最大特征值稱為圖G的無(wú)符號(hào)拉普拉斯譜半徑，記作q(G)。當(dāng)G是連通的，L(G)是一個(gè)不可約矩陣，根據(jù)Perron-Frobenius定理，μ(G)對(duì)應(yīng)的特征向量有一個(gè)正向量，稱μ(G)對(duì)應(yīng)的模為1的正特征向量為L(zhǎng)(G)的perron向量。

圖的譜半徑的研究是譜圖理論中的一個(gè)重要課題。文獻(xiàn)[2]介紹了雙圈圖的譜半徑，文獻(xiàn)[3-6]介紹了給定條件的樹的譜半徑情況，其中文獻(xiàn)[6]介紹了在所有給定階數(shù)及給定獨(dú)立數(shù)的樹中具有最大譜半徑的樹，文獻(xiàn)[7-8]介紹了特定條件下的圖的最大譜半徑以及最小譜半徑。受文獻(xiàn)[6]啟發(fā)，本文給出Tn,α中拉普拉斯譜半徑達(dá)最大的樹，其中下面給出相關(guān)引理。

引理1設(shè)G是一個(gè)連通圖，u,v是圖G中的兩個(gè)點(diǎn)，假設(shè)v1,v2,???,vs(1 ≤s≤d(v ) )是NG(v)NG(u)中的點(diǎn)，X=(x1,x2,???,xn)T是L( G )的Perron向量，其中xi與點(diǎn)vi( 1 ≤i≤n )對(duì)應(yīng)，圖G*是圖G刪去邊vvi( 1 ≤i≤s )，增加邊uvi得到的圖。如果xu≥ xv，那么μ( G ) ＜ μ(G*)。

證明 由文獻(xiàn)[4]可知，引理1對(duì)于無(wú)符號(hào)拉普拉斯譜半徑q( G )是成立的。同時(shí)對(duì)于偶圖G，L( G )和Q(G )具有完全相同的特征值。因?yàn)闃涫桥紙D，故引理1得證。

引理2[6]設(shè)T是一棵樹，Y( T )為樹T中所有葉子的結(jié)合，S( T )為樹T的最大獨(dú)立集，那么，對(duì)于每一個(gè)樹T都存在一個(gè)最大獨(dú)立集S(T )，使得Y( T ) ?S( T )。

現(xiàn)構(gòu)造3種圖，具體如圖1所示。

(1)在星圖K1,e-1中每個(gè)點(diǎn)上粘上至少一條懸掛邊得到的圖，記為n-e；

(2)在星圖K1,e中每個(gè)度為1的點(diǎn)上粘上至少一條懸掛邊得到的圖，記為S2n,n-e；

(3)在星圖K1,e-1中每個(gè)度為1的點(diǎn)上粘上一條懸掛邊，度為e-1的點(diǎn)上粘上n-2e+1條懸掛邊得到的圖，記為S*n,n-e。

圖1

下面給出本文的主要結(jié)果。

定 理1 若T∈Tn,n-e( e ≥2 ) ，則 μ( T ) ≤μ(n-e)，當(dāng)且僅當(dāng)T=,n-e時(shí)等號(hào)成立。

證明 選取樹T∈Tn,n-e( e ≥2)使其拉普拉斯譜半徑盡可能的大。 設(shè)X=(x1,x2,???,xn)T為L(zhǎng)( G )的Perron向量，這里xi與點(diǎn)vi( 1 ≤i≤n )對(duì)應(yīng)，可以得到相關(guān)結(jié)論。

（i）當(dāng)s＞0且t＞0時(shí)，如圖2所示。

根據(jù)引理2，樹T中存在一個(gè)最大的獨(dú)立集S( T )，使得Y( T ) ?S( T )，當(dāng)s＞ 0且t＞ 0時(shí)，有

因?yàn)樵谏鲜鰞煞N變形中

（ii）當(dāng)s=0且t＞0或者s＞0且t=0時(shí)，如圖3所示。

不失一般性，令s=0且t＞0，由引理2，樹T中存在一個(gè)最大的獨(dú)立集S(T ) ，使得Y( T ) ?S( T )，且

因 此 T2∈Tn,n-e，同 理 由 引 理 1，可 得μ( T ) ≤ μ( T2)，矛盾。

（iii）當(dāng)s=0且t=0時(shí)，如圖4所示。

圖2

根據(jù)引理2，樹T中存在一個(gè)最大的獨(dú)立集S( T )，使得Y(T ) ?S( T )，且有

因?yàn)樵谏鲜鰞煞N變形中

因?yàn)樵谏鲜鰞煞N變形中