圖的補圖譜半徑和泛圈性

朱五華，倪貝貝，孫 亮

（安慶師范學院 數學與計算科學學院，安徽 安慶 246133）

圖的補圖譜半徑和泛圈性

朱五華，倪貝貝，孫 亮

（安慶師范學院 數學與計算科學學院，安徽 安慶 246133）

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

補圖；譜半徑；閉包；Hamilton圈；泛圈圖

1 引言

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

設圖G是n階m條邊簡單圖，邊集E=E(G)={e1,e2…en}，設邊數 e(G)=|E(G)|=m，頂點集 V=V(G)={v1,v2…vn}，vi為G中的頂點。 設G=(V,E)是一個n階圖，若對于每一個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中頂點u的度。對于一個簡單圖G=(V,E)，集合E1={uv/u≠v,u,v∈V},G=(V,E1E)稱為G的補圖。設Kn是n階完全圖，K1,n和Kn,m分別是星圖、二部圖，記圖Kn-1+v是Kn-1和一個孤立點的并，Kn-1+e為Kn-1添加一條懸掛邊的圖。本文中一些記號、定義參見文獻。[1]

2 引理

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

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

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

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

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

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

3 主要結果

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

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

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

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

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

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

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

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

證明：(ⅰ)首先證明定理滿足條件時，圖G是Hamilton 圖除非 G=Kn-1+e。 設 H=Cn(G),假設（1）式成立，但G不是Hamilton圖，根據引理2.2，H也不是Hamilton圖，由Cn(G)的性質，對于H中任意兩個不相鄰頂點 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)，關于所有邊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]趙克文,韓烽.哈密爾頓圖與泛圈圖的幾個性質的探討[J].燕山大學學報,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-），安徽太湖人，安慶師范學院數學與計算科學學院碩士研究生，研究方向為圖論與網絡優化。

胡德明