基于无向图的哈密尔顿性存在的若干结果

陈帅君，徐美进，李永明

（辽宁工业大学 理学院，辽宁 锦州 121001）

0 引言

图论以1736年欧拉提出的“哥尼斯堡七桥问题”为起源，经历了近300年的发展沉淀，至今无论是在理论或是应用方面它都有着极其重要的价值. 所谓图论就是对某些点和连接这些点的线所组成集合的某些性质的研究，对于某个连通图来说，经过该图的每条边的迹，称之为欧拉迹；若存在某条路覆盖了每条边恰好一次的回路，称之为欧拉环游，含有欧拉环游的图称之为欧拉图. 若存在某条路覆盖了每个顶点恰好一次，则称之为哈密尔顿路；假如这样的路是一条回路，则称这样的路为哈密尔顿回路；含有哈密尔顿回路的图，称之为哈密尔顿图. 若图中的任意两个顶点都有哈密尔顿路连接着，那么称这类图为哈密尔顿连通图.

图的哈密尔顿性是结构图论一个非常重要而且意义深远的研究课题，该问题的产生和发展与著名的四色猜想研究密切相关，因而备受国内外众多图论专家和学者的关注. 图的哈密尔顿路问题与结构图论中哈密尔顿性的研究也是密切相关的. 从算法复杂性来讲，判定一个图是否存在一条哈密尔顿路是NP-完全的. 对于某个图是欧拉图成立的条件已经解决：一个非空连通图含有欧拉迹当且仅当其最多含有两个奇点；一个非空的连通图是欧拉图当且仅当它没有奇点. 如图1哥尼斯堡七桥图，图2为其简化图. 图2四个顶点都是奇点，因此从任意点出发无法完成每座桥走一次从而走遍全部七座桥的任务，因此图2不是欧拉图且其不含欧拉迹. 但对于哈密尔顿图的判定，还是一个未解之谜，数学家们正在逐渐得使图的哈密尔顿性成立的充分条件更加严格化. 本文第一部分主要简述了图论的发展概述及图的某些基本概念和性质. 第二部分主要概括了某图在参数条件下哈密尔顿图成立的某些条件. 第三部分主要阐述了图在某些禁用子图的条件下哈密尔顿性质成立的某些重要性质，最后针对半无爪图的哈密尔顿性提出了一个有关猜想.

图1 哥尼斯堡七桥图

图2 七桥简化图

1 符号定义

本文中我们考虑的都是阶数为n的有限、无向简单图G= (V(G)，E(G))，即无环也无重边，文中其他未定义到的术语和符号见参考文献［1］. 设G是一个图，其中V(G)和E(G)分别代表图G的顶点集和边集，图G的阶数指V(G)的大小，通常用n表示，Pn表示含有n个顶点的路，d(x)表示顶点x的度数，即与顶点相连的边的条数，d(x，y)表示任意两顶点x，y之间的最短路的长度，称其为两点之间的距离，最小度δ(G)表示图G中度数最小的点的度数，即δ(G)= min{d(v) ，v∈G} ，对于V(G)的任意非空子集S，以S为顶点集，以两端点均在S中的边的全体为边集组成的子图称为G的导出子图. 图G中不含有同构于H的导出子图，则称图G禁用子图H，也称H为图G的禁用子图. 爪（K1，3）是其中一个顶点度是3其余点的度为1的四个顶点组成的连通图，某图的任意导出子图不同构于爪称其为无爪图（K1，3-free）. 对于∀x，y∈V(G)，其中令J(x，y)={u∈N(x)⋂N(y)∶N[u]⊆N[x]⋃N[y]}，当d(x，y)= 2时，J(x，y)≠φ，则称图G是半无爪图. 若图G的顶点的度均为k，则G称为k-正则图. 给定一个整数k，图G的k-正则生成子图称为G的k-因子. 若V(G)的子集V'(G)使得G-V'(G)不连通，则称V'(G)为图G的顶点割，若G中至少有一对相异的不相邻顶点，则G的顶点割元素最少的叫做G的连通度，记为κ(G). 若κ(G)≥k，则称G是k-连通的.

2 通过某些参数角度定义哈密尔顿图

对图的哈密尔顿性质研究最先从图的某些参数出发，这样的性质较为直接，以下两个定理分别在1952年由Dirac［2］和1960年Ore［3］最先提出，在很长一段时间内这是具有标志性作用的两个定理，之后继续引入了图的闭包［4］和独立数［5］等来描述图的哈密尔顿性质.

定理2.1［2］设图G是n阶简单图并且n≥3，图中最小度δ≥n2，则G是哈密尔顿图.

定理2.2［3］设图G是n阶简单图并且n≥3，图中任意两个不相邻的顶点对的度数之和至少为n，则G是哈密尔顿图.

定理2.3［4］设阶数为n的图G包含一个哈密尔顿圈当且仅当反复连接G中所有满足度数之和至少为n的不相邻顶点对，得到的新图G'含有哈密尔顿圈.

1972年V. Chvátal利用β0()G定义图G的独立数，即图G中独立集元素的最大值，得到如下重要定理：

定理2.4［5］设图G的连通度为k，满足β0(G)≤k，则图G是哈密尔顿图.

这些原始定理的提出，开创了一些新的研究方法，提出了图具有哈密尔顿性的充分条件. 在通过其闭包后的新图G'的哈密尔顿性来研究原图的哈密尔顿性，放松了对图的要求，对以后研究某图具有哈密尔顿性具有重要作用. 在这些定理的推广方面，数学家们做了大量的工作，这是哈密尔顿图论的核心课题之一，其他一些结果可参考文献［6-12］.

3 通过某些禁用子图角度定义哈密尔顿图

图的哈密尔顿性问题是结构图论中极其重要且意义深远的一个课题，禁用子图与图的很多性质都有着密切的联系，比如，禁用子图与图的哈密尔顿连通性，禁用子图与图的染色、2 -因子，禁用子图与图的泛圈性等问题都有密切的联系.

自从Beineke在1970年发表了有关线图性质的文章后［13］，大家开始研究无爪图的性质. 在线图都是无爪图这个研究背景下，二十世纪七八十年代，对于无爪图的路圈性质的研究也开始起来了，如果图G中不含有同构于K1，3（完全二部图）的导出子图，则称图G是无爪图（K1，3-free），也称K1，3是该图的禁用子图，K1，3-free同理可知.

关于禁用子图与图的哈密尔顿连通性问题的研究，在1979年D. J. Oberly［14］和G. Chartrand［15］率先提出如下定理：

定理3.1［14］任意的阶数n≥3的连通的、局部连通无爪图G是哈密尔顿图.

定理3.2［15］一个3 -连通的、局部连通无爪图是哈密尔顿连通的.

后来，1984年Kanetkar和Rao［16］严格化了G. Chartrand的上述定理，将3 -连通改为2 -连通并证明了其结果的正确性.

1985年M. M. Matthews和D. P. Summer［17］也得到了关于无爪图有Hamilton圈的重要结果：

定理3.3［17］设图G是n阶2 -连通无爪图，如果∀v∈V(G)，d(v)≥(n- 2)3，则G中含有哈密尔顿圈，即图G是哈密尔顿图.

1986年，刘一萍等［18］用三个不相邻顶点的度和条件得到了无爪图有Hamilton圈的充分条件：

定理3.4［18］设图G是n阶2 -连通无爪图，如果δ3()G≥n- 2，那么图G中含有哈密尔顿圈，即图G是哈密尔顿图.

1989年，E. Flandrin［19］等人给出了下面的结果：

定理3.5［19］设图G是n阶2 -连通无爪图，如果G中任意一对不相邻的顶点u，v满足d()u+d()

v≥(2n- 5)3，则G有Hamilton圈.

1996年，A. S. Asratian［20］在定理3.2的基础之上提出并证明了如下结论：

定理3.6［20］设图G是局部连通的无爪图，则G是哈密尔顿连通的当且仅当图G是3 -连通的.

2012年，马修山，王江鲁［21］证明了下面结果：

定理3.7［21］设图G是n阶2 -连通无爪图，如果G中任意两个同构于K2（2阶完全图）的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 3，则G有Hamilton圈.

2013年，徐珊珊，王江鲁［22］将其扩展至3 -连通无爪图上研究，提出了如下两个定理：

定理3.8［22］设图G是n阶2 -连通无爪图，如果G中任意两个分别同构于P（33个顶点的路）和K（22阶完全图）的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 2，则G有Hamilton圈.

定理3.9［22］设图G是n阶3 -连通无爪图，如果G中任意两个分别同构于K（33阶完全图）和K1的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 3，则G有Hamilton圈.

2014年，米晶［23］证明了如下结论：

定理3.10［23］设图G是n阶2 -连通无爪图，如果G中任意两个分别同构于P3和K1的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n，则G中含有Hamilton圈.

定理3.11［23］设图G是n阶2 -连通无爪图，如果G中任意两个分别同构于K3和K2的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 3，则G有Hamilton圈.

同年，孙运伟［24］研究无爪图的路圈性质后得到了以下结论：

定理3.12［24］设图G是n阶2 -连通无爪图，如果G中任意两个分别同构于K1和K2的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 3，则G的任意最长圈是Hamilton圈，特别的，这里说明了其下届“n-3” 是最好的.

2016年，郑伟，王力工［25］得到如下相关定理：

定理3.13［25］设图G是n阶3 -连通且最小度δ(G)≥4的无爪图，如果G中任意两个分别同构于P（44个顶点的路）和K1的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n，则G是哈密尔顿连通的.

2016年，尹君［26］利用导出圈的性质来判断图的哈密尔顿性，证明了以下定理：

定理3.14［26］对于3 -连通的线图，若它不含长度超过8的导出圈，则该图是哈密尔顿图，同时证明了对于3 -连通的无爪图，若它的每个长度至少为4的导出圈中至多含有8条非奇异边，则该无爪图是哈密尔顿图；若它每个长度至少为4的导出圈中至多含有11条非奇异边，则要么它是哈密尔顿图，要么它的闭包是经过收缩可变为Petersen图（图3）的线图.

图3 Petersen图

定理3.15［26］任意2 -连通的无爪图，若它最长的导出圈的长度不小于n- 2，那么该图是哈密尔顿图.

定理3.16［26］最小度δ≥3的n阶无爪图，若它含有长度超过(4n- 2δ- 4)δ+2的导出圈，则它是哈密尔顿图. 然后证明了当δ∈{ 3，4} 时，上述结果是最好的.

2018年，Benjamin Momège［27］在K1，4-free图哈密尔顿性研究方向上得到新的进展，如下：

定理3.17［27］若连通图G的最小度δ(G)≥2n3并且图G是K1，4-free的，则G中包含了一条哈密尔顿路.

2020年，石开欣，任韩［28］得到以下结论：

定理3.18［28］设图G是n阶3 -连通无爪图，如果G中任意两个分别同构于K1和P4的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 2，则G有Hamilton圈.

定理3.19［28］设图G是n阶3 -连通无爪图，其中n≥12，如果G中任意两个分别同构于K2和P4的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 3，则G有Hamilton圈.

定理3.20［28］设图G是n阶3 -连通无爪图，满足δ(G)≥4，如果G中任意两个分别同构于K2和P4的不相邻子图点H1和H2的度之和满足d(H1)+d(H2)≥n- 1，则G是哈密尔顿连通的.

近年来，由无爪图引申出另一新的概念：半无爪图［29］. 对图G中任意距离为2的点x和y，存在u∈N(x)⋂N(y)，满足N(u)⊆N(x)⋃N(y)，则G称为半无爪图. 一个图是无爪图(CF)，则该图一定也是半无爪图(QCF)，反之则不成立，即CF∈QCF，因此半无爪图是对无爪图的一定程度上的扩展，许多满足无爪图哈密尔顿性的条件在半无爪图上同样适用. 关于半无爪图的哈密尔顿性有如下重要定理：

定理3.21［29］一个κ-连通的半无爪图G(κ≥2)，如果α(G2)≤κ，则G是哈密尔顿图.

在Fan-type条件下P. Bedrossian［31］将Fan［30］的结果进行了轻微的改善，A. Ainouche［29］又在这一基础之上行了如下改进：

定理3.22［30］设图G是一个阶数n≥3的2 -连通图，令u和v是G中不相邻的两个顶点，满足d( u，v)=2 ⇒max(d(u)，d(v))≥n2，则G中有哈密尔顿圈.

定理3.23［31］设图G是阶数为n的2 -连通图，若d(x，y)= 2 ⇒max{d(x)，d(y)}≥n2对于G的导出爪图（K1，3）或导出修正爪图（K1，3+e，e是一条边）中的每一对顶点都成立，则G是哈密尔顿图.

定理3.24［29］设图G是一个2 -连通的简单图，图G满足条件d(x，y)= 2，{z∈N(x)⋂N(y)|d(z)= 2} =φ并且d(x)≤d(y)

定理3.25［29］若图G是κ-连通的半无爪图(κ≥2)，如果对于G中的任意基数为κ+1的独立集X，都有则G是哈密尔顿图.

2007年，孙淑霞［32］在上述定理的基础上证明了：

定理3.26［32］若图G是κ-连通的半无爪图(κ≥2)，如果对于G2中的任意基数为κ+1的独立集X，都有则G是哈密尔顿图.

2019年，陈晓东［33］对半无爪图的Ore哈密尔顿充分性条件进行了改进，提出如下定理：

定理3.27［33］对任意的阶数为n的半无爪图G，若σk+1(G)≥n-k（k是正整数），则p(G)≤k，其中σk+1(G)是图G中k+1个顶点的独立集中的最小度和，p(G)= min{ | Ρ |：Ρ是一条覆盖G的路}.

针对李明楚［34］在1993提出的关于无爪图的某条哈密尔顿性质，2003年李饶［35］证明了原条件同样适用于半无爪图，如下：

定理3.28［34］设图G是n阶3 -连通无爪图并且最小度δ(G)≥(n+5)5，则图G是一个哈密尔顿图.

定理3.29［35］设图G是n阶3 -连通半无爪图并且最小度δ(G)≥(n+5)5，则图G是一个哈密尔顿图.

同样的类似推理，李饶［37］证明了如下的无爪的哈密尔顿图的性质在半无爪图中同样适用：

定理3.30［36］设图G是n阶2 -连通无爪图并且最小度δ(G)≥n4，则图G是一个哈密尔顿图或者G∈ℑ，ℑ为连通度为2的非哈密尔顿图的集合.

定理3.31［37］设图G是n阶2 -连通半无爪图并且最小度δ(G)≥n4，则图G是一个哈密尔顿图或者G∈ℑ，ℑ为连通度为2的非哈密尔顿图的集合.

定理3.32［27］设图G是一个阶数为n的连通图，如果G是K1，4-free的并且σ2(G)≥2n3，则图G包含一条哈密尔顿路.

引理3.1［27］设图G是一个阶数为n的图并且1 ≤k≤k' ≤n，则σk'(G)≥(k'σk'(G))k.

猜想3.1 设图G是一个阶数为n的连通图，如果G是σ3(G)≥n的半无爪图，则图G包含一条哈密尔顿路.

4 结束语

图的哈密尔顿性的研究在生活中有着极其广泛的应用，例如近年来兴起的快递服务业，寻找尽可能短的一条路线走完所有的目的地，就是一类典型的哈密尔顿应用问题. 本文针对无向图的哈密尔顿性成立的各类条件，在某些参数或禁用子图的先决条件下，以时间为顺序，对无向图的哈密尔顿性成立的各类条件进行了概括梳理. 而后结合部分定理，给出一个相关猜想.