Hamiltonian cycles in 2-tough 2K_2-free graphs
Hamiltonian cycles in 2-tough 2K_2-free graphs
复制标题
2-韧 2K_2-自由图中的哈密顿循环
DOI：
10.1002/jgt.22852
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
K. Ota and M. Sanka
中科院分区：
文献类型：
--
作者：
N. Matsumoto;R. Moriyama and K. Ota;K. Ota and M. Sanka
如果图 G $G$ 不包含 2 K2 $2{K}_{2}$ 作为诱导子图，则称为 2 K2 $2{K}_{2}$ 无图。 2014 年，Broersma、Patel 和 Pyatkin 证明，至少三个顶点上的每个 25-tough 2 K2 $2{K}_{2}$-free 图都是哈密顿量。最近，Shan 改进了这一结果，证明 3-tough 就足够了，而不是 25-tough。在本文中，我们证明了至少三个顶点上的每个 2-tough 2 K2 $2{K}_{2}$-free 图都是哈密顿量，这是由 Gau 和 Pasechnik 猜想的。
A graph G $G$ is called a 2 K2 $2{K}_{2}$‐free graph if it does not contain 2 K2 $2{K}_{2}$ as an induced subgraph. In 2014, Broersma, Patel, and Pyatkin showed that every 25‐tough 2 K2 $2{K}_{2}$‐free graph on at least three vertices is Hamiltonian. Recently, Shan improved this result by showing that 3‐tough is sufficient instead of 25‐tough. In this paper, we show that every 2‐tough 2 K2 $2{K}_{2}$‐free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.