第二大特征值不超過的樹圖

阮曉露, 吳曉霞,2,3*

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,福建漳州363000；2.數(shù)字福建氣象大數(shù)據(jù)研究所,福建漳州363000；3.數(shù)據(jù)科學(xué)與統(tǒng)計重點實驗室,福建漳州363000）

設(shè)G=(V(G),E(G))是n階簡單圖,記P(G,x)= det(xI-A(G))為G的特征多項式,A(G)為其鄰接矩陣.A(G)的特征值為G的特征值.因為A(G)是實對稱矩陣,所以A(G)的特征值都為實數(shù),不妨設(shè)λ1(G)≥λ2(G)≥…≥λn(G).樹是連通無圈圖,記T是一個樹圖，Pn代表n個頂點的路，若V′?V(G),E′={uv∈E(G)|u,v∈V′},則稱G′=(V′,E′)是G中由V′生成的導(dǎo)出子圖.

1982 年,Cvetkovi?[1]提出確定λ2(G)≤1 的圖類,對于這個問題,經(jīng)過研究者們多年的努力,當(dāng)前關(guān)于特征值確定的圖類已有許多研究結(jié)果,但仍未徹底解決,1993 年Cao[2]刻畫了λ2(G)<的簡單圖,Cheng[3]刻畫了λ2(G)≤1 且僅有三個特征值的簡單圖.由于確定出λ2(G)≤1的所有圖較難,研究者們開始利用第二大特征值刻畫特殊的圖類,1982 年Neumaier[4]給出了樹圖第二大特征值的重要性質(zhì),1998 年Shu[5]刻畫了λ2(T)≤1的樹圖,2012年Stani?[6]刻畫出λ2(T)≤的樹圖,2021年Liu[7]刻畫出不包含K1,3,K5-e作為導(dǎo)出子圖且λ2(G)≤1 的圖.利用Neumaier[4]提出的關(guān)于樹圖第二大特征值的性質(zhì),給出了λ2(G)≤的樹圖的充要條件.

1 預(yù)備知識

引理1[4]1)設(shè)u是－圖G的任意頂點,C(u)是在圖G中包含頂點u的所有圈集,則

2)設(shè)uv是圖G的任意邊,C(uv)是在圖G中包含邊uv的所有圈集,則

引理2[8]設(shè)G=(V(G),E(G))是n階圖,V′?V(G)且|V′|=k,則

引理3[9]設(shè)G是n階簡單圖,則λ1(G)≥λ1(Pn)當(dāng)且僅當(dāng)G?Pn時等號成立.

引理4[4]設(shè)G?G1∪G2∪…∪Gω()G,則

引理5[4]設(shè)T是n階樹且λ2(T)≤λ,則

1)要么存在點u∈V(T),使得λ1(T-u)≤λ；

2)要么存在邊uv∈E(T),使得T-uv=T1∪T2,有λ1(T1-u)<λ<λ1(T)且λ1(T2-v)<λ<λ1(T).

2 主要結(jié)論

定理1記T是樹,則λ1(T)≤ 3 當(dāng)且僅當(dāng)T同構(gòu)于K1,3或Pi,i= 1,2,…,5 是其中之一,特別地λ1(P5)=λ1(K1,3)=.

證明充分性計算K1,3或Pi,i= 1,2,…,5的第一大特征值可得結(jié)論成立；

必要性 設(shè)樹T,|V(T)|=n且λ1(T)≤,假設(shè)n> 5,由引理3可知

這與λ1(T)≤矛盾,故n≤5,計算得

如圖1,從而T只能同構(gòu)于K1,3或Pi,i= 1,2,…,5是其中之一,證畢.

圖1 點變換圖Fig.1 Vertex transformation graph

在下面敘述和證明中,將涉及一類圖,圖1的T′和圖2的T″,在T′中,si(i= 1,…,12)是任意正整數(shù)且至少有一個不為零,代表著K1,3和Pi,i= 1,2,…,5用其任意的頂點(除去同構(gòu)的情況)連接點u的數(shù)目,例如當(dāng)s2=2,s10= 3,si= 0,i≠2,10 時,T′?Tˉ；同理在T″中,ki(li),i= 1,…,6 是任意正整數(shù)且至少有一個不為零,代表著Pi,i= 1,2,…,4 用其任意的頂點(除去同構(gòu)的情況)接點u(v)的數(shù)目.

圖2 邊變換圖Fig.2 Edge transformation graph

定理2記T是樹,令u為樹T中的一個點,則λ1(T-u)≤當(dāng)且僅當(dāng)T?T′(如圖1),其中Si(i=1,…,12)是正整數(shù)且至少有一個不為零.

證明充分性因為T?T′,所以

從而由引理4,定理2可知

必要性 若d(u)= 1,則u是T的懸掛點,因為λ1(T-u)≤由定理1 可知T-u同構(gòu)于P1,P2,P3,P4,P5,K1,3其中之一,從而T?T′,其中僅存在一個si≠0.若d(u)=k≥2,則u是T的割點,從而T-u=T1∪T2∪…∪Tk,k≥2,不妨設(shè)λ1(T1)≥λ1(T2)≥…≥λ1(Tk),因為≥λ1(T-u)=λ1(T1),由定理2可知Ti同構(gòu)于P1,P2,P3,P4,P5,K1,3(i= 1,2…,k)其中之一,從而T?T′.其中至少存在si,sj,i≠j不為零,證畢.

定理3記T是樹,令uv為樹T中的一條邊,使得T-uv=T1∪T2,則λ1(T1-u)<<λ1(T)且λ1(T2-v)<λ1(T)當(dāng)且僅當(dāng)T?T″(如圖2),ki,li,i= 1,…,6至少有一個不為零.

證明充分性 如圖2 所示,T?T″,T-uv=T1∪T2,T1-u=k1?P1∪k2?P2∪(k3+k4)?P3∪(k5+k6)?P4,從而由引理4,定理2 可知同理λ1(T2-v)<.

必要性 因為T-uv=T1∪T2,所以d(u)≥2,u是T1的割點,從而妨設(shè)λ1(T11)≥λ1(T12)≥…≥λ1(T1k),因為由定理2,T i1(i= 1,…,k)只能同構(gòu)于Pi,i= 1,…,4 其中之一,同理T2-u=T12∪T22∪…∪T l2,(l≥2),T i2(i= 1,…,l)也只能同構(gòu)于Pi,i=1,…,4其中之一,從而T?T″,證畢.

定理4若T?T″.λ2(T″)≤ 3 當(dāng)且僅當(dāng)ki,li,i= 1,…,6滿足表1中的取值.

證明令Pi(x)為Pi的特征多項式,根據(jù)引理1可得：

則

其中

取V′={u,v},|V′|= 2,則

計算得

令a=(6 - 2k1- 3k2- 4k3- 6k4- 6k5- 12k6),b=(6 - 2l1- 3l2- 4l3- 6l4- 6l5- 12l6),因為λ1(T1-由引理2,可知同理即a< 0 且b< 0,由于ki,li,i= 1,…,6 是正整數(shù),因為a=k且b=l與a=l且b=l,T″同構(gòu),所以a,b的取值滿足以下情況：

1)a= -1且b= -1,…,或- 12；2)a= -2且b= -3,…,或- 6；3)a= -3且b= -4.

滿足上述情況的ki,li,i= 1,…,6的取值見表1,證畢.

表1 ki(li)(i = 1,…,6)的取值Tab.1 The values of ki(li)(i = 1,…,6)

續(xù)表1

續(xù)表1

定理5設(shè)T是樹,λ2(T)≤當(dāng)且僅當(dāng)

1)T要么是T′的任意導(dǎo)出子圖；

2)T要么是T″的任意導(dǎo)出子圖,其中ki,li,i= 1,…,6滿足表1中的取值.

證明必要性 設(shè)樹T,λ2(T)≤,由引理5 的1）與定理2 可知,T?T′,由引理2 可知,T′的任意導(dǎo)出子圖由引理5的2）與定理2可知T?T″,其中ki,li,i= 1,…,6滿足表1中的取值,同理由引理2可知,T″的任意導(dǎo)出子圖

充分性 當(dāng)T?T′,由引理2 可知,從而T′的任意導(dǎo)出子圖,第二大特征值也小于；當(dāng)T?T″,由定理4 可知,ki,li,i= 1,…,6 滿足表1 中的取值時,有從而T″的任意導(dǎo)出子圖,第二大特征值都小于證畢.