王 磊，蔡改香，刘 莉

（安庆师范大学数理学院，安徽安庆246133）

设G=(V(G),E(G))是n阶简单图，其顶点集为V=V(G)，边集为E=E(G)。记Gc=(V,Ec)为图G=(V,E)的补图，其中Ec={xy:x,y∈V,x≠y,xy∉E}。顶点v的度d G(v)指G中与v关联的边数，G的最大度与最小度分别记为Δ(G)和δ(G)。图G的邻接矩阵A(G)=[aij]n×n，当vi、vj相邻时，aij=1，否则aij=0，i,j=1,2,3,…,n。A(G)的最大特征值μ(G)称为G的谱半径。设S⊆V，图G[S]表示以S为顶点集，以G中两端点均在S中的边为边集的图，若图G[S]中无边，则称S为G的独立集。G中含点数最多的独立集所含点数称为G的独立数，记为α(G)。如果G中所有顶点的度都相等，则称图G为正则图。如果Δ(G)=δ(G)=n-1，则称G为完全图，记作Kn。如果图的顶点集V可以被划分为互不相交的子集X和Y，使得V=X⋃Y，且任意边uv满足u∈X，v∈Y或u∈Y，v∈X，则称G为二部图，记作GBPT=(X,Y;E)。若对任意u∈X，d GBPT(u)相同，且任意v∈Y，d GBPT(v)也相同，则称GBPT为二部半正则图。设G1=(V1,E1)，G2=(V2,E2)是2个顶点不相交的简单图，它们的并图为G1⋃G2=(V1⋃V2,E1⋃E2)，联图为G1∨G2=((G1)c⋃(G2)c)c。对于非负整数k，若连续连接图G中的度和不小于k的不相邻点对，直到没有这样的点对存在，所得到的图称为图G的k-闭包，记作clk(G)。图G的k-闭包是唯一确定的，与所增加的边的次序无关，并且在clk(G)中任意不相邻点对u，v，有d clk(G)(u)+d clk(G)(v)≤k-1。其余相关概念和术语可参考文献[1]。

如果一条闭路径的起点和内部顶点互不相同，则称它为圈，一条包含图G中所有顶点的路称为哈密尔顿路，一个包含图G中所有顶点的圈称为哈密尔顿圈。若图G包含一个哈密尔顿圈，则称图G是哈密尔顿图。若图G中任意两个顶点都被一条哈密尔顿路连接，则称G是哈密尔顿-连通图。设X是图G的任意顶点集且X⊂V(G)，这里X中顶点数为s，如果图G-X是哈密尔顿-连通图，则称图G是s-哈密尔顿-连通图。……