Hamiltonian cycles in 2-tough 2K₂-free graphs

2021/03/11 by Ota, Katsuhiro, Sanka, Masahiro · 1 citation
#05C38 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2103.06760

Abstract

A graph G is called a 2K₂-free graph if it does not contain 2K₂ as an induced subgraph. In 2014, Broersma, Patel and Pyatkin showed that every 25-tough 2K₂-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 2K₂-free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.

Cited by

• Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs

Related

• Hamiltonian cycles in 3-tough 2K₂-free graphs
• Hamilton cycles in tough (2P₂ ∪ P₁)-free graphs
• Some conditions for hamiltonian cycles in 1-tough (K₂ ∪ kK₁)-free graphs
• Hamiltonian cycles in 7-tough (P₄∪ P₁)-free graphs
• Every 2k-connected (P₂∪ kP₁)-free graph with toughness greater than one is hamiltonian-connected