圖的補(bǔ)圖譜半徑和泛圈性

朱五華，倪貝貝，孫 亮

（安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133）

圖的補(bǔ)圖譜半徑和泛圈性

朱五華，倪貝貝，孫 亮

（安慶師范學(xué)院 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133）

設(shè)G=(V,E)是一個(gè)n階簡單圖，若對于每一個(gè)k(3≤k≤n)，G都含有長度為k的圈Ck，則稱G為泛圈圖。利用圖的閉包理論研究圖的補(bǔ)圖譜半徑的界，討論了泛圈圖存在的一個(gè)譜條件。

補(bǔ)圖；譜半徑；閉包；Hamilton圈；泛圈圖

1 引言

隨著圖論研究的不斷發(fā)展，圖的泛圈性問題也成為研究者熱點(diǎn)研究課題之一。本文通過對圖的補(bǔ)圖譜半徑的刻畫，并利用圖的閉包理論，研究了泛圈圖存在的譜條件。

設(shè)圖G是n階m條邊簡單圖，邊集E=E(G)={e1,e2…en}，設(shè)邊數(shù) e(G)=|E(G)|=m，頂點(diǎn)集 V=V(G)={v1,v2…vn}，vi為G中的頂點(diǎn)。 設(shè)G=(V,E)是一個(gè)n階圖，若對于每一個(gè)k(3≤k≤n)，G都含有長度為k的圈Ck，則稱G為泛圈圖。A(G)=(aij)n×n稱為圖G的鄰接矩陣，其中如果 vi鄰接 vj，則 aij=1，否則 aij=0。 A(G)的最大特征值稱為G的譜半徑，記作μ(G)。dG(u)表示G中頂點(diǎn)u的度。對于一個(gè)簡單圖G=(V,E)，集合E1={uv/u≠v,u,v∈V},G=(V,E1E)稱為G的補(bǔ)圖。設(shè)Kn是n階完全圖，K1,n和Kn,m分別是星圖、二部圖，記圖Kn-1+v是Kn-1和一個(gè)孤立點(diǎn)的并，Kn-1+e為Kn-1添加一條懸掛邊的圖。本文中一些記號(hào)、定義參見文獻(xiàn)。[1]

2 引理

給定整數(shù)k≥0,G中任意兩個(gè)不相鄰頂點(diǎn)u，v∈G，如果有 d(u)+d(v)≥k，則在 G中加一條邊(u,v)，得到G1=G+(u,v)，對G1進(jìn)行類似的添加邊程序，直到不再有這樣的頂點(diǎn)為止得到圖Ck(G),那么稱Ck(G)為G的k-閉包。

引理2.1[2]：設(shè)簡單圖G的階為n，對于G中任意兩個(gè)不相鄰頂點(diǎn)u，v∈G，都有

(ⅰ)n階圖G有一條Hamilton路當(dāng)且僅當(dāng)閉包Cn-1(G)有一個(gè)Hamilton路；

(ⅱ)n階圖G有一條Hamilton圈當(dāng)且僅當(dāng)閉包Cn(G)有一個(gè)Hamilton圈。

引理2.2[3]：一個(gè)簡單圖G是Hamilton圖當(dāng)且僅當(dāng)它的閉包C(G)是Hamilton圖。

引理2.3[4]：設(shè)G是一個(gè)n階m條邊的連通圖，假設(shè)m=(n-12)+l，如果l≥0,則G包含一條Hamilton路除非 G=Kn-1+v，如果 l≥1，則 G包含一條 Hamilton圈除非G=Kn-1+e。

3 主要結(jié)果

引理3.1：設(shè)G是n(n≥6)階m條邊的簡單連通圖，如果G中包含一條Hamilton圈且m≥(n-12)+1，則 Cn上存在鄰接的兩點(diǎn) u，v，使得 d(u)+d(v)≥n+1。

證明：設(shè)Cn上任意鄰接的兩點(diǎn)u，v，有d(u)+d(v)≤n，則有

引理 3.2[5]： 若x，y是n階圖G的Cn上鄰接的兩點(diǎn)，且 d(x)+d(y)≥n+1，則 G有同時(shí)過 x，y的 Cr(r=3，4,…，n)。

證明：Cn標(biāo)號(hào)為：x1x2…xnx1，使 d(x1)+d(x2)≥n+1。設(shè)k為滿足3≤k+2≤n的任一自然數(shù)，若有含x1、x2的Ck+2，則引理成立。

若沒有 Ck+2,有兩種情況，情況(ⅰ)：路 xn-(k-1)xn-k…x3上若有點(diǎn) xh與 x2相鄰， 則路 P2：xk+2xk+3…xn上的點(diǎn) xh+k-1與 x1不相鄰。 因?yàn)槿?xh+k-1與 x1相鄰，就有 Ck+2：x2xhxh+1…xh+k-1x1x2，與假設(shè)沒有 Ck+2矛盾。情況(ⅱ)：路 xnxn-1…xn-(k-2)上若有點(diǎn) xn-r與 x2相鄰，則路 P1：x3x4…xk+1上的點(diǎn) xk+1-r與 x1不相鄰。 因?yàn)槿粲?xk+1-r與 x1相鄰，就有 Ck+2：x1xk+1-r…x2xn-rxn-r+2…x1，與假設(shè)沒有 Ck+2矛盾。

這兩種情況考慮了與x2相鄰的點(diǎn)全在V（G）{x1,x2}中，相應(yīng)有一一對應(yīng)的與x1不相鄰的點(diǎn)也全在V（G）{x1,x2}中，而 x1與 x1不相鄰，從而有 d(x1)≤n-(d(x2)-|(x1)|-|(x1)|)，得到：d(x1)+d(x2)≤n，與引理?xiàng)l件矛盾,引理得證。

定理3.3：設(shè)G是一個(gè)n(n≥6)階m條邊的簡單連通圖，μ()是G的補(bǔ)圖的譜半徑，如果

則G是泛圈圖除非G=Kn-1+e。

證明：(ⅰ)首先證明定理滿足條件時(shí)，圖G是Hamilton 圖除非 G=Kn-1+e。 設(shè) H=Cn(G),假設(shè)（1）式成立，但G不是Hamilton圖，根據(jù)引理2.2，H也不是Hamilton圖，由Cn(G)的性質(zhì)，對于H中任意兩個(gè)不相鄰頂點(diǎn) u，v∈H，有 dH(u)+dH(v)≤n-1,則有 dH(u)+dH(v)=n-1-dH(u)+n-1-dH(v)≥n+1，對任意的 uv∈C(H)，關(guān)于所有邊uv∈E(H)對不等式求和，獲得

[1]Bondy J A,Murty U S R.Graph theory with applications[M].London:Macmillan,1976:1-10.

[2]0.Ore.Note on Hamilton circuits[J].The American Mathematical monthly,1960,67(1):55.

[3]J.A.Bondy,and V.Chvátal.A method in graph theory[J].Discrete Mathematics,1976,15:111-136.

[4]M.Fiedler,V.Nikiforov.Spectral radius and Hamiltonicity of graphs[J].Linear Algebra and its Applications,2010,432:2170-2173.

[5]趙克文,韓烽.哈密爾頓圖與泛圈圖的幾個(gè)性質(zhì)的探討[J].燕山大學(xué)學(xué)報(bào),2001,25(3):227-229.

[6]M.Hofmeister.Spectral radius and degree sequence[J].Mathematische Nachrichten,1988,139:37-44.

Spectral Radius of Complement Graphs and Pancyclism of Graphs

Zhu Wuhua，Ni Beibei,Sun Hang

(School of Mathematics and Computational Science,Anqing Teachers'College,Anqing246133,China)

Letbe a simple graph of order,is called pancyclic graph if it contains a cycle of length for all.In this paper we discuss the existence of some spectral conditions of pancyclic graph by using bounds of spectral radius with closure theory of the Complement of a graph.

complement graph;spectral radius;closure;Hamilton cycle;Pancyclic graph

O157.5

A

1672-447X（2012）03-0008-002

2011-11-07

朱五華（1982-），安徽太湖人，安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院碩士研究生，研究方向?yàn)閳D論與網(wǎng)絡(luò)優(yōu)化。

胡德明