由星補(bǔ)刻畫(huà)的一類(lèi)廣義線(xiàn)圖

袁名焱,羅秋紅，湯自凱

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 中國(guó) 長(zhǎng)沙 410081)

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

矩陣A的特征值稱(chēng)為圖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)

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

雞尾酒會(huì)圖C(Pn)是完全圖K2n去掉一個(gè)由n條邊組成的完美匹配,C(P0)表示空?qǐng)D.

由圖譜理論[5]可知廣義線(xiàn)圖的最小特征值λmin≥-2, 而且除了廣義線(xiàn)圖之外只有有限個(gè)連通圖的最小特征值也大于等于-2, 這類(lèi)圖稱(chēng)之為例外圖, 例外圖最多有36個(gè)頂點(diǎn)[6-7].關(guān)于星補(bǔ)圖的其他相關(guān)文獻(xiàn)請(qǐng)參考[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, 我們把這種方法稱(chēng)為禁忌子圖技巧.

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

圖1 Smith圖

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

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

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

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

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

2 Ct+2sK1作為特征值-2的星補(bǔ)

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

(3)

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

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

(4)

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

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

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時(shí),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時(shí), 有M(S1)=0,M(S2)=8,再由等式(3)易得|S2|=4, 1°得證.

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

(5)

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

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

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

且星補(bǔ)H里的孤立頂點(diǎn)總數(shù)為偶數(shù), 即s為非負(fù)偶數(shù), 故把星補(bǔ)記成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.