图的补图谱半径和泛圈性

朱五华，倪贝贝，孙 亮

（安庆师范学院 数学与计算科学学院，安徽 安庆 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-），安徽太湖人，安庆师范学院数学与计算科学学院硕士研究生，研究方向为图论与网络优化。

胡德明