一類樹圖的第二大特征值

彭海根,吳曉霞,2*

（1.閩南師范大學數學與統計學院,福建漳州363000;2.數據科學與統計重點實驗室,福建 漳州363000）

圖1 樹T(1,b,c)Fig.1 Tree T(1,b,c)

1 預備知識

圖2 最大特征值屬于(2,)的連通圖Fig.2 Connected graphs with the largest eigenvalue in(2,)

2 主要結果

下面的討論主要根據選取樹圖T(1,b,c)(其中c ≥b ≥5)不同的割點u來得到G -{ }u 不同的子圖序列，借助引理5，給出其第二大特征值不同的界，從而得到更好的界.這個界只與其子圖Pc,Pc-1,Pc-2,Pc-3有關.根據確定的界可以給出T(1,b,c)依第二大特征值的排序.為了簡便后面的證明，我們先計算一些簡單結果:

1) 只有一個頂點的圖G，有λ1(G)= 0. 事實上，因為只有一個頂點的圖G 的特征多項式為χ(G,λ)= λ，所以λ1(G)= 0.

根據圖類T(1,b,c)的結構，下面只需討論圖類T(1,b,c)在c ≥b的情形.下面定理2證明中對圖G割點u 的選取有兩種情形，一種是使圖G -{u } 的分支H1和H2結構相同頂點數盡可能相等，以此得到更好的界，另一種是先選一個使λ1(H1)盡可能小的割點，得到λ2(T(1,b,c))的上界，再選一個使λ1(H2)盡可能大的割點，得到λ2(T(1,b,c))的下界.

定理2 設樹圖G = T(1,b,c)，若c ≥b ≥5，則

定理3 設樹圖T(1,b,c)，其中c ≥b ≥7，則有λ2(T(1,b - 2,c + 2))＞λ2(T(1,b,c)).

證明 當b + 2 ≥c ≥b 時，由定理2 中1)的證明知λ1(Pc)≥λ2(T(1,b,c)). 因為b ≥7，所以b - 2 ≥5，又因 為6 ≥c + 2 -(b - 2)≥4，所 以 由 定 理2 中2)的 證 明 可 知λ2(T(1,b - 2,c + 2))＞λ1(Pc). 因 此λ2(T(1,b - 2,c + 2))＞λ2(T(1,b,c)).根據定理2中1)的證明知，當c = b + 3時，λ2(T(1,b,c))= λ1(Pc-1)，又因為當c ＞b + 3 時，由定理2 中2)和3)的證明知，λ1(Pc-1)＞λ2(T(1,b,c))，所以當c ≥b + 3 時，λ1(Pc-1)≥λ2(T(1,b,c)). 當c ≥b + 3 時，c + 2 -(b - 2)≥7，由定理2 中3)的證明知λ2(T(1,b - 2,c +2))＞λ1(Pc-1)，所以λ2(T(1,b - 2,c + 2))＞λ2(T(1,b,c))，證畢.

3 總結

根據引理5中結果,對樹圖T(1,b,c)割點進行選取得到其第二大特征值的界，為了確定第二大特征值的分布,采用兩種方式選取樹圖T(1,b,c)的割點,一種是選取使H1和H2結構相同頂點數盡可能相等的割點，另一種是先選一個使λ1(H1)盡可能小的割點得到T(1,b,c)第二大特征值的上界,再選一……