
arXiv: 2103.06760
A graph $G$ is called a $2K_2$-free graph if it does not contain $2K_2$ as an induced subgraph. In 2014, Broersma, Patel and Pyatkin showed that every 25-tough $2K_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 $2K_2$-free graph on at least three vertices is Hamiltonian, which was conjectured by Gao and Pasechnik.
14 pages. We have noticed that one of our results, showing that every $\frac{3}{2}$-tough $2K_2$-free graph on at least three vertices has a 2-factor, is an immediate corollary to a known result. So, we have just described the result on 2-factors as a proposition, and have omitted our proof (Section 3 in the previous version) in the paper. Accordingly, we have changed the title. $ \ $
Eulerian and Hamiltonian graphs, 05C38, Hamiltonian cycle, \(2K_2\)-free graph, FOS: Mathematics, toughness, Mathematics - Combinatorics, Combinatorics (math.CO), 2-factor, Paths and cycles
Eulerian and Hamiltonian graphs, 05C38, Hamiltonian cycle, \(2K_2\)-free graph, FOS: Mathematics, toughness, Mathematics - Combinatorics, Combinatorics (math.CO), 2-factor, Paths and cycles
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
