恰有兩個(gè)主特征值的三圈圖

湯自凱，侯耀平

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，中國 長沙 410081)

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

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

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

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

在文獻(xiàn)[2]中Hagos給出了圖恰有2個(gè)主特征值的充要條件.

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

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

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

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

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

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

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

(1)當(dāng)b≥0時(shí)，Gu只有1個(gè)頂點(diǎn)；

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

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

(2)假設(shè)當(dāng)b<0時(shí)，u在Gu中的離徑RGu(u)≥3.設(shè)P=u0u1u2…uk(uk=u)是Gu中長為k=RGu(u)的一條路，則u0必為懸掛點(diǎn)，從而根據(jù)度線性得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.

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

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

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

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

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

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

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

容易證得：

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

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

定理1設(shè)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的值

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

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

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

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

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

(1.1.1.1)存在一點(diǎn)x∈NP(w),d(x)=2.設(shè)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及頂點(diǎn)度線性得d(v)=6,d(w)=3,a=3,b=0,則?w∈N(v),d(w)=3,G?G1(如圖1).

(1.1.1.2)存在一點(diǎn)x∈NP(w),d(x)>2.由引理4知P上所有頂點(diǎn)的度相等,所以d(x)=d(w)=a+b.對于頂點(diǎn)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)進(jìn)行討論.

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

當(dāng)dB(v)≠d(v)時(shí)，即d(v)=a+b,dB(v)

(1.1.2)P的長度等于1.

對于頂點(diǎn)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āng)d(v)=4,d(u)=4時(shí)，得a(d(w)-1)=6.當(dāng)a=3時(shí)，d(w)=3,b=0,設(shè)頂點(diǎn)u的另3個(gè)鄰點(diǎn)為z1,z2,z3,則度序列分別為(3，3，3)或(3，4，2).當(dāng)度序列為(3，3，3)時(shí)，G?G12(如圖2)；當(dāng)度序列為(3，4，2)時(shí)，G?G13(如圖2).當(dāng)a=2時(shí)，d(w)=4,b=2,設(shè)頂點(diǎn)u的另3個(gè)鄰點(diǎn)為z1,z2,z3,則度序列為(2，2，2)，G?G4(k=1)(如圖2).當(dāng)a=1時(shí)，d(w)=7,b=6,設(shè)頂點(diǎn)u的另3個(gè)鄰點(diǎn)z1,z2,z3,則度序列為(1，1，1)，矛盾.

當(dāng)d(v)=d(u)=a+b>3時(shí)，得(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)當(dāng)dB(v)=d(v)且dB(w)≠d(w)時(shí)，由引理5知G?G14或G?G5(如圖2).

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

(1.2.3)當(dāng)dB(v)=d(v)≥3且dB(w)=d(w)≥3時(shí)，由引理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個(gè)主特征值的三圈圖

由引理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,假設(shè)存在wi,d(wi)=2,則對于wi有2a+b≥a2+ab-a+1+2,3a+b≥a(a+b)+3,當(dāng)a+b=2時(shí)，2a+2≥2a+3矛盾，當(dāng)a+b>2時(shí)，3a+b≥a(a+b)+3，矛盾，所以d(wi)>2.

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

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

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

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

(2)當(dāng)p=5時(shí)，引理5及引理10知，wi中恰有4個(gè)度為a2+ab-a+1與1個(gè)3度點(diǎn).則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,無滿足條件的整數(shù)解.

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

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

當(dāng)d(wi)=a2+ab-a+1或d(wi)=3時(shí)，設(shè)wi中k個(gè)頂點(diǎn)度為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只有惟一整數(shù)解：k=0,a=3,b=-1,此時(shí)G?G43.

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

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

當(dāng)k=1時(shí)，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,只有惟一整數(shù)解：d=3,a=3,b=-1.不妨設(shè)d(w1)=3,d(w2)=a(a+b-1)+1=4,則w2也必與3-度點(diǎn)相鄰，3-度點(diǎn)的鄰點(diǎn)的度序列必為(2，2，4)，2-度點(diǎn)的鄰點(diǎn)的度序列必為(2，3)或(1，4)，4-度點(diǎn)的鄰點(diǎn)的度序列(4，3，2，2)由引理5知B=sk(G)只能是圖(1)中的l,m,n,o中的一種且階為28，所以G?G44或G45或G46或G47或G48(如圖3).

當(dāng)k=0時(shí),由引理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有惟一整數(shù)解a=3,b=-1.此時(shí)w1,w2的度序列只能是(3,4),對于4度點(diǎn)的鄰點(diǎn)中必有2個(gè)2度點(diǎn),與G是三圈圖矛盾.所以k=0時(shí)滿足條件的G不存在.

由定理1和定理2得到下面的結(jié)果.

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

參考文獻(xiàn)：

[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] 侯耀平,周后卿.恰有兩個(gè)主特征圖的樹[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào),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.