论文标题
关于汉密尔顿周期的注释，价格为$ 4 $ -tough $（p_2 \ cup kp_1）$ - 免费图形
A note on hamiltonian cycles in $4$-tough $(P_2\cup kP_1)$-free graphs
论文作者
论文摘要
令$ t> 0 $为真实数字，$ g $为图。我们说$ g $是$ t $ -tough如果对于$ g $的每个切割$ s $ s $，则$ | s | $与$ g-s $的组件的比例至少为$ t $。 Chvátal的韧性猜想，表明存在一个恒定的$ T_0 $，因此每$ T_0 $ -TOUGH图与至少三个顶点都是Hamiltonian，它仍然是开放的。对于任何给定的整数$ k \ ge 1 $，如果$ g $不包含$ p_2 $和$ k $隔离的顶点，则图$ g $是$（p_2 \ cup kp_1）$免费。 在本说明中，我们表明，每4-Tough和$ 2K $连接的$（P_2 \ CUP KP_1）$ - 至少三个顶点的免费图是Hamiltonian。 从某种意义上说，此结果是经典chvátal-erdős的“扩展”，即每个$ \ max \ {2，k \} $ - 连接 $（k+1）p_1 $ - 至少三个顶点上的免费图是哈密顿人。
Let $t>0$ be a real number and $G$ be a graph. We say $G$ is $t$-tough if for every cutset $S$ of $G$, the ratio of $|S|$ to the number of components of $G-S$ is at least $t$. The Toughness Conjecture of Chvátal, stating that there exists a constant $t_0$ such that every $t_0$-tough graph with at least three vertices is hamiltonian, is still open in general. For any given integer $k\ge 1$, a graph $G$ is $(P_2\cup kP_1)$ free if $G$ does not contain the disjoint union of $P_2$ and $k$ isolated vertices as an induced subgraph. In this note, we show that every 4-tough and $2k$-connected $(P_2\cup kP_1)$-free graph with at least three vertices is hamiltonian. This result in some sense is an "extension" of the classical Chvátal-Erdős Theorem that every $\max\{2,k\}$-connected $(k+1)P_1$-free graph on at least three vertices is hamiltonian.
