编辑推荐:
摘要我们引入一种闭包运算,将无爪图G转换为图Gˉ,使得G是Gˉ的生成子图,Gˉ是某个多图的线图,且Gˉ是2-哈密顿的当且仅当G是2-哈密顿的。我们还给出了若干应用。章节摘要术语与符号本文中,用图表示有限简单无向图G=(V(G),E(G));若允许多重边,我们总是称之为多图。我
摘要
我们引入一种闭包运算,将无爪图G转换为图,使得G是的生成子图,是某个多图的线图,且是2-哈密顿的当且仅当G是2-哈密顿的。我们还给出了若干应用。
章节摘要
术语与符号
本文中,用图表示有限简单无向图;若允许多重边,我们总是称之为多图。我们通常遵循最通用的图论符号和术语,关于基本概念和符号请参见例如[2]。具体而言,若图F是G的子图,我们记作,若F是G的诱导子图,则记作。若G不包含图F作为诱导子图的副本,则称G为F-自由图。具体而言,
预备知识
本节总结我们在证明中将用到的一些已知结果。
2-哈密顿性的闭包
本节给出一种构造方法,对于给定的无爪图G,得到它的2-哈密顿闭包(缩写为2h-闭包)。
设
G为无爪图,设
为由以下构造从
G得到的图。
- 1.
若G不是4-连通的,选取一个顶点割,其中,记为的连通分支,并令。
- 2.
若G是4-连通且2-哈密顿的,令。
- 3.
若
G是4-连通但不是2-哈密顿的,则
按如下方式获得。
主要结果
以下定理是本文的主要结果。
定理1
设G是连通的无爪图,设是它的一个2h-闭包。则- 1.
G是2-哈密顿的当且仅当是2-哈密顿的,
- 2.
存在一个多图H使得。
证明
1. 若G不是4-连通的,或者G是4-连通且2-哈密顿的,则陈述1是显然的。若G是4-连通但不是2-哈密顿的(即定义的第3步适用),则证明由定理E、定理I以及一个明显的事实得出
应用
1. 以下结果在[9]中得到证明。
定理L
[9] 每个最小度至少为6的5-连线图都是2-哈密顿的。
另一方面,以下结果在[20]中得到证明。
定理M
[20]
以下命题等价:- (i)
每个4-连线图都是哈密顿的。
- (ii)
每个4-连通无爪图都是1-哈密顿连通的。
现在,若Thomassen猜想(定理M的陈述(i))为真,则任何5-连通无爪图都是2-哈密顿的,因为删除其任意一个顶点都得到一个4-连通的
结论性评述
注意,有时k-哈密顿性以稍强的方式定义,即当对每个满足的都是哈密顿的时,称G为k-哈密顿的(而不是我们定义中的条件)。因此,按此更强意义,图G是k-哈密顿的当且仅当(根据我们的定义)G对所有满足的s都是s-哈密顿的(其中当然"0-哈密顿"意味着"哈密顿")。然而,[9]中也证明了每个最小度至少为6的5-连通无爪图都是
Zdeněk Ryjá?ek|Petr Vrána|Liming Xiong