1-坚韧分裂图的Prism-哈密顿性

Prism-Hamiltonicity of 1-Tough Split Graphs

摘要: 如果对于图$G$ 的任意割集$S\subseteq V\left(G\right)$ 均有$\left|S\right|/c\left(G-S\right)\ge t$ ，则称图$G$ 是$t$ -坚韧的，其中$c\left(G-S\right)$ 表示$G-S$ 的分支数。1973年，Chvátal猜想存在常数$t_0$ 使得每个阶数$n\ge 3$ 的$t_0$ -坚韧图都是哈密顿图，该猜想对于一般图至今仍未解决。图$G$ 的Prism定义为笛卡尔积$G\square K_2$ ，如果$G\square K_2$ 是哈密顿图，则称$G$ 是Prism-哈密顿图。Kaiser等猜想存在常数$t_1$ ，使得每个$t_1$ -坚韧图都是Prism-哈密顿图，并证明了若该猜想成立，则$t_1\ge 9/8$ 。Kratsch等证明了每个3/2-坚韧的分裂图都是哈密顿图，并构造了一系列坚韧度小于3/2且非哈密顿的分裂图，从而3/2是保证分裂图成为哈密顿图的最佳坚韧度下界。本文从更弱的坚韧度条件出发，研究了1-坚韧分裂图的Prism-哈密顿性，证明了Kaiser等的猜想对于1-坚韧的分裂图成立。

Abstract: A graph $G$ is $t$ -tough if $\left|S\right|/c\left(G-S\right)\ge t$ for every cutset $S\subseteq V\left(G\right)$ , where $c\left(G-S\right)$ denotes the number of components of $G-S$ . In 1973, Chvátal conjectured that there exists a constant $t_0$ such that every $t_0$ -tough graph of order $n\ge 3$ is Hamiltonian. This conjecture remains open for general graphs. The prism of a graph $G$ is defined as the Cartesian product $G\square K_2$ . A graph $G$ is called prism-Hamiltonian if $G\square K_2$ is Hamiltonian. Kaiser et al. conjectured that there exists a constant $t_1$ such that every $t_1$ -tough graph is prism-Hamiltonian, and proved that if the conjecture holds, then $t_1\ge 9/8$ . Kratsch et al. proved that every 3/2-tough split graph is Hamiltonian and constructed a family of non-Hamiltonian split graphs with toughness less than 3/2, showing that 3/2 is the best possible toughness lower bound for guaranteeing Hamiltonicity in split graphs. In this paper, starting from a weaker toughness condition, we study the prism-Hamiltonicity of 1-tough split graphs and prove that Kaiser’s conjecture holds for 1-tough split graphs.