嚴亞偉，葉淼林，蘆興庭

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

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

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

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

證明 由文獻[4]可知，引理1對于無符號拉普拉斯譜半徑q( G )是成立的。同時對于偶圖G，L( G )和Q(G )具有完全相同的特征值。因為樹是偶圖，故引理1得證。

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

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

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

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

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

圖1

下面給出本文的主要結果。

定 理1 若T∈Tn,n-e( e ≥2 ) ，則 μ( T ) ≤μ(n-e)，當且僅當T=,n-e時等號成立。

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

（i）當s＞0且t＞0時，如圖2所示。

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

因為在上述兩種變形中

（ii）當s=0且t＞0或者s＞0且t=0時，如圖3所示。

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

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

（iii）當s=0且t=0時，如圖4所示。

圖2

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

因為在上述兩種變形中

因為在上述兩種變形中