朱五华，倪贝贝，孙 亮

（安庆师范学院 数学与计算科学学院，安徽 安庆 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。……