袁名焱,羅秋紅，湯自凱

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

設(shè)G為簡單圖, 記G的頂點集為V(G)={1,2,…,n},G的鄰接矩陣為A=(aij), 其中

矩陣A的特征值稱為圖G的特征值.

1 一些引理

引理1[3](重構(gòu)定理) 若圖G的鄰接矩陣為

(1)

其中Ax表示圖G的導(dǎo)出子圖X的鄰接矩陣, 則X是圖G關(guān)于特征值μ的星集當(dāng)且僅當(dāng)μ不是矩陣C的特征值, 且

μI-Ax=BT(μI-C)-1B.

(2)

給定一個圖H, 假設(shè)U為頂點集V(H)的子集, 且頂點v?V(H). 把頂點v和頂點集U中的每個頂點都相連, 從而得到圖H(U), 如果μ不是圖H的特征值, 卻是圖H(U)的特征值, 我們稱U是特征值μ的好集. 可知星集里任何一頂點vi在星補H的鄰集Ui都是好集.

雞尾酒會圖C(Pn)是完全圖K2n去掉一個由n條邊組成的完美匹配,C(P0)表示空圖.

由圖譜理論[5]可知廣義線圖的最小特征值λmin≥-2, 而且除了廣義線圖之外只有有限個連通圖的最小特征值也大于等于-2, 這類圖稱之為例外圖, 例外圖最多有36個頂點[6-7].關(guān)于星補圖的其他相關(guān)文獻(xiàn)請參考[8～12].

注1假設(shè)U是特征值μ的好集, 即μ是圖H(U)的特征值, 如果λmin(H)>μ, 由插值定理知μ是圖H(U)的最小特征值.

注2假設(shè)圖G的λmin(G)=-2, 圖G′為圖G的導(dǎo)出子圖, 由插值定理[4]知：λmin(G′) ≥-2, 即不存在圖G′為圖G的導(dǎo)出子圖使得λmin(G′)<-2, 我們把這種方法稱為禁忌子圖技巧.

已知Smith圖是一類最大特征值為2的連通簡單圖，見圖1，圖T1(n),T2(n)中n表示圖的階數(shù).

圖1 Smith圖

推論1[8]若Smith圖不為奇圈, 則最小特征值為-2.

我們稱Smith圖的連通導(dǎo)出子圖為簡化Smith圖.

推論2[8]任何簡化Smith圖的最小特征值大于-2.

引理2[8]任何一個異于圖C3,C5,C7的Smith圖G加一條懸掛邊(或加多條懸掛邊)得到圖H,則λmin(H)<-2.

引理3[4]假設(shè)一個連通非二部圖H有n個頂點,m條邊, 則線圖L(H)的特征值-2的重數(shù)K=2m-n. 當(dāng)H為連通二部圖時,K=m-n+1.

2 Ct+2sK1作為特征值-2的星補

設(shè)圖G是以H=Ct+2sK1為特征值-2的星補的連通圖,C表示圖H的鄰接矩陣,X表示特征值-2的星集,v為星集里任意一頂點, 由引理1的(2)式得：bTMb=8, 其中b為頂點v的刻畫向量,M=4(2I+C)-1. 設(shè)M=(mij), 則

(3)

令M(S)=bTMb=8, 其中頂點集S表示頂點v在星補H里的鄰集, 換句話說,S是頂點v的好集：S={u∈V(H):u～v}, 則M(S)是由頂點集S決定的矩陣M中的主子陣各元素之和. 不妨設(shè)S1表示頂點v在圈Ct里的鄰集：S1={u∈V(Ct):u～v},S2表示頂點v在孤立點集2sK1里的鄰集：S2={u∈V(2sK1):u～v}.

M(S)=M(S1)+M(S2)=8.

(4)

引理5[9]假設(shè)t為大于3的奇數(shù),S1表示頂點集V(Ct)的子集,若|S1|為偶數(shù), 不妨設(shè)|S1| =2h, 則M(S1)≥4h. 等號成立當(dāng)且僅當(dāng)S1是由V(Ct)中的h對相鄰的點組成.

引理6當(dāng)t為大于1的奇數(shù)時, 圖G是以H=Ct+2sK1作為特征值μ=-2的星補, 則星集X里的頂點v的好集U有以下3類：

1° {qi,qj,qk,ql}(qr∈V(2sK1),r∈{i,j,k,l}),

2° {pi,pi+1,qk,ql}(pr∈V(Ct),r∈{i,i+1})(qw∈V(2sK1),w∈{k;l}),

3° {pi,pi+1,pj,pj+1}(pr∈V(Ct),r∈{i,i+1,j,j+1}).

證由等式(4)知M(S)=M(S1)+M(S2)=8. 假設(shè)|S1|為奇數(shù), 由等式(3)知，當(dāng)it,j>t時,mij為非負(fù)偶數(shù), 從而M(S2)為非負(fù)偶數(shù), 這與等式(4)矛盾, 即|S1|只能為非負(fù)偶數(shù). 不妨設(shè)|S1|=2h, 由引理5得：M(S1)≥4h,且M(S)=M(S1)+M(S2)=8. 所以非負(fù)整數(shù)h只能取0,1或2. 當(dāng)h=0時, 有M(S1)=0,M(S2)=8,再由等式(3)易得|S2|=4, 1°得證.

當(dāng)h=1時, 不妨設(shè)S1={pi,pj}, 其中j>i. 由等式(3)得

(5)

由等式(5), |M(S1)|=4(mod8). 結(jié)合等式(4)得M(S1)=M(S2)=4, 且pi,pj為圈Ct上一對相鄰的頂點, 即pi,pj可表示為pi,pi+1. 由M(S2)=4得|S2|=2. 不妨設(shè)S2={qk,ql}為任意2個孤立頂點,2°得證.

當(dāng)h=2時, 由引理5得M(S1)≥8. 結(jié)合等式(4), 有M(S1)=8, 且|S1|=4是圈Ct上兩對相鄰的點.不妨設(shè)S1={pi,pi+1,pj,pj+1}, 3°得證.

引理7當(dāng)t為大于1的奇整數(shù)時, 設(shè)圖G是以H=Ct+2sK1為特征值-2的星補的連通圖,用X1表示星集X里好集屬于類型1°的集合,X2表示星集X里好集屬于類型2°的集合,X3表示星集X里好集屬于類型3°的集合. 則

且星補H里的孤立頂點總數(shù)為偶數(shù), 即s為非負(fù)偶數(shù), 故把星補記成H=Ct+2sK1.

圖2 圖G(1)，G(2)，G(3),其中λmin(G(1))=-2.192 58, λmin(G(2))=-2.039 73, λmin(G(3))=-2.166 96.

參考文獻(xiàn)：

[1] BELL F K, POWLINSON P. On the multiplicities of graph eigenvalues[J]. Bull London Math Soc, 2003，35(3):401-408.

[2] ROWLINSON P. On multiple eigenvalues of trees[J]. Linear Algebra Appl, 2010，423(11):3007-3011.

[8] BELL F K, SLOBODAN K S. On graphs whose star complement for -2 is a path or a cycle[J]. Linear Algebra Appl, 2004,377:249-265.

[9] BELL F K. Characterizing line graphs by star complements[J]. Linear Algebra Appl, 1999,296(1-3):15-25.

[10] ELLINGHAM M N. Basic subgraphs and graph spectra[J]. AUS J Comb,1993(8):247-265.

[11] ROWLINSON P. Star partitions and regularity in graphs[J]. Linear Algebra Appl, 1995，226-228:247-265.

[12] ROWLINSON P, BELL F K. Graph eigenspace of small codimension[J].Discrete Math, 2000，220:1-3.