恰有兩個主特征值的三圈圖

湯自凱，侯耀平

(湖南師范大學數學與計算機科學學院，中國 長沙 410081)

設G=(V，E)是簡單連通圖，V(G)和E(G)分別為圖G的頂點集與邊集，記n(G)=|V(G)|為圖G的階，dG(v)(或d(v))為頂點v在圖G中的度，δ(G),Δ(G)分別表示圖G的頂點的最小度與最大度，度為i的頂點稱為i-度點，1-度點通常也稱為懸掛點.設矩陣A=A(G)為圖G的鄰接矩陣，λ1,λ2,…,λn是A(G)的特征值，也稱為圖G的特征值.若G有一個相應于特征值λ的各分量之和不為零的特征向量，則稱λ為G的一個主特征值.容易看出圖恰有一個主特征值當且僅當它是正則圖.恰有k(k≥2)個主特征值的圖的刻畫是圖譜理論中一個未解決的公開問題[1].Hagos在文獻[2]中給出了恰有2個主特征值的圖的一個充要條件，侯耀平，胡智全，I.Gutman, S.Grünewald等在文獻[3～10]中給出了恰有2個主特征值圖的一些結構性質及刻畫了一些特殊的恰有2個主特征值的圖，如所有恰有2個主特征值的樹，單圈圖與雙圈圖，譜半徑為3且恰有2個主特征值的整圖等.本文刻畫了所有恰有2個主特征值的三圈圖，它們有無限多個，但只具有48個不同的結構形式，其中有懸掛點的21種，無懸掛點的27種.

先介紹度線性、調和圖、骨胳圖、柄點、離徑等概念.頂點u與v在圖G中相鄰記為u～v.令

m(v)稱為v的二次度.圖G稱為是(a,b)-度線性的，如果存在唯一的一對有理數a,b,使對G中任何v∈V(G),均有：S(v)=ad(v)+b.(a,0)-度線性圖也稱為二次度正則的，或調和圖[5-7].

設G是帶圈圖，記B=sk(G)為G不斷刪除圖中1-度點得到的新圖，稱圖sk(G)為G的骨骼圖.則δ(sk(G))≥2.設v是圖G的一個頂點，如果v的鄰點中恰有2個頂點不是懸掛點，則稱v為圖G的一個柄點(knob).容易看出，(a,b)-度線性圖中的柄點的度必為2或a+b.圖G中頂點v的離徑RG(v)定義為：RG(v)=maxu∈V(G)d(v,u).設G是含圈連通圖，割邊e=uv,且滿足G-e的2個連通分支一個是樹，另一個是帶圈圖，分別記Gu,Gv,我們稱頂點u為v的外鄰點，記所有v的外鄰點的集合為O(v),v的鄰點集中不屬于O(v)中頂點的集為內鄰點集，記為I(v).設Tv={v}∪u∈O(v)Gu.

在文獻[2]中Hagos給出了圖恰有2個主特征值的充要條件.

引理1[2]設G是一個連通圖.則圖G恰有2個主特征值的充要條件是圖G是度線性的.

引理2[3]設圖G是(a,b)-度線性圖.則a,b一定是整數.

引理3[4]設圖G是(a,b)-度線性圖，如果圖G中存在一個恰有a+b-1>0個懸掛點的頂點u，則這個圖只可能是樹Tα或雙星圖Sb+1,b+1.

引理4[4]設v0,v1,v2,v3,v4是(a,b)-度線性圖G中的一條路或一個圈(v0=v4時)，v1,v2,v3都是柄點且v0,v4不是懸掛點，記pi=di-2,i=1,2,3為與vi相鄰的懸掛點數目，如果p1>0,則d(v0)=d(v1)=d(v2)=d(v3)=d(v4).

引理5設G是三圈圖，sk(G)是圖G的骨胳圖.則δ(sk(G))≥2,Δ(sk(G))≤6，且sk(G)圖必是圖1中的一種.

圖1 三圈圖G的sk(G)圖的可能圖

引理6G是n個頂點，m條邊(m≥n)的(a,b)-度線性圖.如果G中存在一條割邊e=uv,圖G-e連通分支為Gu,Gv,其中Gu是無圈圖.則

(1)當b≥0時，Gu只有1個頂點；

(2)當b<0時，則Tv中除v外任一葉子w到v的距離相等且RTv(v)≤3.

證(1)的證明見文獻[3].

(2)假設當b<0時，u在Gu中的離徑RGu(u)≥3.設P=u0u1u2…uk(uk=u)是Gu中長為k=RGu(u)的一條路，則u0必為懸掛點，從而根據度線性得d(u1)=a+b,d(u2)=a2+ab-a+1,d(u3)=(a+b-1)(1-ab)+1,d(u4)=d(u3)(a-d(u2))+b+d(u2).

因d(u2)-a=a(a+b-2)+1≥1,所以d(u4)≤-d(u3)+b+d(u2)<0,矛盾.所以RTv(v)≤3.

假設存在2個葉子w1,w2,d(v,w1)=k1≠d(v,w2)=k2,因k1≠k2對兩條路利用度線性的定義可分別計算各點的度得d(v)的值不相等，矛盾.所以當b<0時，則Tv中除v外任一葉子w到v的距離相等且RTv(v)≤3.

證引理1.5知Tv中除v外任一葉子w到v的距離相等且RTv(v)=k≤3.假設RTv(v)=3,此時b<0,a≥3.設w是到v的距離為3的葉子，wu2u1v是w到v的路，由度線性的定義計算得d(u2)=a+b,d(u1)=d(u)=a2+ab-a+1,d(v)=(a+b-1)(1-ab)+1.

(2)當a+b-2=0時，a+b=2,a≥3,即d(u3)=1,d(u2)=2,d(u1)=a+1,d(v)=2-2a+a2=(a-1)2+1.

假設wi中有一個頂點w的度為d(w)≤3.當d(w)=3時，由ad(w)+b=3a+b≥d(v)+4=2-2a+a2+4得(a-2)2≤a+b-2=0矛盾；當d(w)=2時，由ad(w)+b=2a+b≥d(v)+2=2-2a+a2+2得(a-2)2≤b<0矛盾.假設錯誤，即任一wi中頂點的度為d(wi)>3.

由(1)(2)，命題7得證.

下面分2種情況進行討論：(1)離徑小于等于1且恰有2個主特征值的三圈圖;(2)離徑等于2且恰有2個主特征值的三圈圖.

1 離徑小于等于1且恰有2個主特征值的三圈圖

容易證得：

引理8設G=(V，E)是(a,b)-度線性n階圖，(1)如果G中存在2個長度為3的路，它們的度序列分別為(x,2,y)，(w,2,z),則x+y=w+z.

(2)記m為G的邊數，若m>n,則G中不存在3個連續的2-度點.

定理1設G是(a,b)-度線性三圈圖，B=sk(G)且?v∈B,RTv(v)≤1,則G只能是如圖2所示的42種中的一種，且(a,b)-度線性三圈圖a,b的值見表1.

表1 RTv(v)≤1的(a,b)-度線性三圈圖a,b的值

證設G是(a,b)-度線性三圈圖，B=sk(G)且?v∈B,RTv≤1.dG(v),NG(v)分別表示頂點v在圖G中的度與鄰點的集合，為了書寫簡便記d(v)=dG(v),N(v)=NG(v).由引理5知，?v∈B且dB(v)>2,w∈NB(v).下面分dB(w)=2與dB(w)>2進行討論.

(1)當?w∈NB(v)且d(w)>2時，對于w分兩種情況討論.

(1.1)dB(w)=2.由度線性的定義可得d(w)=a+b.設P是圖B中的一條從w出發到頂點u(dB(u)>2)的路(u可能與v重合).

圖2 RTv(v)≤1的(a,b)-度線性三圈圖

(1.1.1)存在路P的長度大于等于2.

(1.1.1.1)存在一點x∈NP(w),d(x)=2.設NP(x)=w,y,則d(w)+d(y)=2a+b,故d(y)=a≥2.因dB(w)=2,d(w)>2,故d(v)+d(x)+d(w)-2=ad(w)+b,即d(v)=a(d(w)-1)≥2(d(w)-1)≥4.由引理5及頂點度線性得d(v)=6,d(w)=3,a=3,b=0,則?w∈N(v),d(w)=3,G?G1(如圖1).

(1.1.1.2)存在一點x∈NP(w),d(x)>2.由引理4知P上所有頂點的度相等,所以d(x)=d(w)=a+b.對于頂點w，d(v)+d(x)+d(w)-2=ad(w)+b,因而d(v)=(a-1)(d(w)-1)+1,由引理5知d(v)=6,5,4,3或a+b.分dB(v)=d(v)與dB(v)≠d(v)進行討論.

當dB(v)=d(v)時.d(v)只能等于3，4，5.當d(v)=5時，必有d(w)=3；a=3,b=0時，則?w∈N(v),d(w)=3,G?G2(如圖2)；當d(v)=4時，必有d(w)=4；a=2,b=2時，則頂點v相鄰的點的度序列只能為(2，2，2，4)，與2-度點的鄰點的度序列只能為(2，4)，所以圖G是如圖2中G3，G4中的一種.當d(v)=3時，必有d(w)=3；a=2,b=1時，則頂點v相鄰的點的度序列只能為(2，2，3)，與2-度點的鄰點度序列只能為(2，3)，所以圖G是圖2中的G6，G7，G8，G9，G10，G11中的一種.

當dB(v)≠d(v)時，即d(v)=a+b,dB(v)

(1.1.2)P的長度等于1.

對于頂點w,有d(v)+d(u)+d(w)-2=ad(w)+b,得d(v)+d(u)=a(d(w)-1)+2.由引理5及度線性知d(v),d(u)只能取(4，4)或(a+b,a+b).

當d(v)=4,d(u)=4時，得a(d(w)-1)=6.當a=3時，d(w)=3,b=0,設頂點u的另3個鄰點為z1,z2,z3,則度序列分別為(3，3，3)或(3，4，2).當度序列為(3，3，3)時，G?G12(如圖2)；當度序列為(3，4，2)時，G?G13(如圖2).當a=2時，d(w)=4,b=2,設頂點u的另3個鄰點為z1,z2,z3,則度序列為(2，2，2)，G?G4(k=1)(如圖2).當a=1時，d(w)=7,b=6,設頂點u的另3個鄰點z1,z2,z3,則度序列為(1，1，1)，矛盾.

當d(v)=d(u)=a+b>3時，得(a-2)(a+b-1)=0,又a+b>3,所以a=2,b=2,G?G5(k=1)(如圖2).

(1.2)?w∈NB(v),dB(w)>2.

(1.2.1)當dB(v)=d(v)且dB(w)≠d(w)時，由引理5知G?G14或G?G5(如圖2).

(1.2.2)當dB(v)≠d(v)且dB(w)≠d(w)時，由引理5知G?G15(如圖2).

(1.2.3)當dB(v)=d(v)≥3且dB(w)=d(w)≥3時，由引理5知G為圖2中G13，G17，G20，G22，G24，G26，G28，G32，G35，G37，G38，G40的一種.

(2)?w∈NB(v),d(w)=2.即此圖G的最小度大于等于2.由引理6與引理8知圖G存在分別為圖2中的G16～G42.

2 離徑等于2且恰有2個主特征值的三圈圖

由引理7知RTv(v)<3,下面討論?v∈B,RTv(v)=2的情況.

證由于RTv(v)=2.由引理1.5知b<0.記d(u)=a+b,d(v)=a2+ab-a+1=a(a+b-1)+1,假設存在wi,d(wi)=2,則對于wi有2a+b≥a2+ab-a+1+2,3a+b≥a(a+b)+3,當a+b=2時，2a+2≥2a+3矛盾，當a+b>2時，3a+b≥a(a+b)+3，矛盾，所以d(wi)>2.

假設存在wi,d(wi)=a+b.對于wi有,ad(wi)+b>d(v)+d(wi)-1,即a+b>a+b矛盾，因此d(wi)≠a+b.

假設k=p,由度線性得(a+b-1)(pa-p+ba)=0，所以p-ba=pa.方程p-ba=pa沒有滿足2≤p≤6,a+b≥2,b<0的整數解，矛盾.所以k

圖3 RTv(v)=2的(a,b)-度線性三圈圖

(1)當p=6時，引理5及引理10知d(wi)=a2+ab-a+1(1≤i≤6)矛盾.

(2)當p=5時，引理5及引理10知，wi中恰有4個度為a2+ab-a+1與1個3度點.則S′=5(a+b)-ba(a+b-1)=4(a2+ab-a+1)+3(5-4),得(a+b-1)(5-ba-5a)=2.方程(a+b-1)(5-ba-5a)=2,無滿足條件的整數解.

(3)當p=4時，同(2)可得a,b無滿足條件的整數解.

(4)當p=3時，引理5及引理10知d(wi)=a2+ab-a+1或d(wi)=d(3≤d≤5);

當d(wi)=a2+ab-a+1或d(wi)=3時，設wi中k個頂點度為a2+ab-a+1(0≤k≤2),則S′=3(a+b)-ba(a+b-1)=k(a2+ab-a+1)+3(3-k),得(a+b-1)(3-ba-ka)=6-2k.不定方程(a+b-1)(3-ba-ka)=6-2k只有惟一整數解：k=0,a=3,b=-1,此時G?G43.

當wi中有一個度d(wi)=d=5或6時，同理可得a,b無滿足條件的整數解.

(5)當p=2時，由引理5及引理10知，d(wi)=a2+ab-a+1或d(wi)=d(3≤d≤6).設wi中有k個度為a2+ab-a+1(0≤k≤1)的頂點.

當k=1時，S′=2(a+b)-ba(a+b-1)=a2+ab-a+1+d,得(a+b-1)(2-ba-a)=d-1.不定方程(a+b-1)(2-ba-a)=d-1,只有惟一整數解：d=3,a=3,b=-1.不妨設d(w1)=3,d(w2)=a(a+b-1)+1=4,則w2也必與3-度點相鄰，3-度點的鄰點的度序列必為(2，2，4)，2-度點的鄰點的度序列必為(2，3)或(1，4)，4-度點的鄰點的度序列(4，3，2，2)由引理5知B=sk(G)只能是圖(1)中的l,m,n,o中的一種且階為28，所以G?G44或G45或G46或G47或G48(如圖3).

當k=0時,由引理5及引理10知，w1,w2的度序列只能是(3,3),(3,4),(3,5),(4,4),則S′=2(a+b)-ba(a+b-1)=d(w1)+d(w2),得4≤(a+b-1)(2-ba)≤6.因2-ba≥5,故a+b=2.a,b有惟一整數解a=3,b=-1.此時w1,w2的度序列只能是(3,4),對于4度點的鄰點中必有2個2度點,與G是三圈圖矛盾.所以k=0時滿足條件的G不存在.

由定理1和定理2得到下面的結果.

推論1恰有2個主特征值的三圈圖只有如圖2,3中的48種.

參考文獻：

[1] CVETKOVIC D, ROWLINSON P, SIMIC S. Eigenspaces of graphs[M].Cambrige:Cambridge University Press, 1997.

[2] HAGOS E M. Some results on graph spectra[J]. Linear Algebra Appl, 2002,356(1-3):103-111.

[3] HOU Y P, TIAN F. Unicyclic graphs with exactly two main eigenvalues[J]. Appl Math Letters, 2006,19(11):1143-1147.

[4] 侯耀平,周后卿.恰有兩個主特征圖的樹[J].湖南師范大學自然科學學報,2005,28(2):1-3.

[6] HU Z Q, LI S C, ZHU C F. Bicyclic graphs with exactly two main eigenvalues[J]. Lin Algebra Appl, 2009, 413(10):1848-1857.

[7] TANG Z K, HOU Y P. The integral graphs with index 3 and exactly two main eigenvalues[J]. Lin Algebra Appl, 2010,433(5):984-993.

[8] GRüNEWALD S, STEVANOVIC D. Semiarmonic bicyclic graphs[J]. Appl Math Letters, 2005,18(11):1228-1238.

[9] DRESS A, GRüNEWALD S. Semiharmonic trees and monocyiclic graphs[J]. Appl Math Letters, 2003,16(8):1329-1332.

[10] DRESS A, GRüNEWALD S, STEVANOVIC D. Semiharmonic graphs with fixed cyclomatic number[J]. Appl Math Letters, 2004,17(6):623-629.