Special Issue in Memory of Sergei Duzhin (1956–2015); Guest Editors: S. V. Chmutov, M. V. Karev, L. H. Kauffman and J. H. PrzytyckiNo Access

Edge-dominating cycles, $k$ -walks and Hamilton prisms in $2 K_{2}$ -free graphs

Gao Mou

School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

E-mail Address: gaom0002@e.ntu.edu.sg

Search for more papers by this author

and

Dmitrii V. Pasechnik

Department of Computer Science, The University of Oxford, Oxford, UK

E-mail Address: dimpase@cs.ox.ac.uk

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0218216516420116Cited by:1 (Source: Crossref)

Abstract

We show that an edge-dominating cycle in a $2 K_{2}$ -free graph can be found in polynomial time; this implies that every $\frac{1}{k - 1}$ -tough $2 K_{2}$ -free graph admits a $k$ -walk, and it can be found in polynomial time. For this class of graphs, this proves a long-standing conjecture due to Jackson and Wormald [ $k$ -walks of graphs, Australas. J. Combin.2 (1990) 135–146]. Furthermore, we prove that for any $ϵ > 0$ every $(1 + ϵ)$ -tough $2 K_{2}$ -free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.

To the memory of Sergei Duzhin.

Keywords:

AMSC: 05C45, 05C85

References

1. E. Balas and C. S. Yu, On graphs with polynomially solvable maximum-weight clique problem, Networks 19(2) (1989) 247–253. Crossref, Web of Science, Google Scholar
2. D. Bauer, H. Broersma and E. Schmeichel, Toughness in graphs—a survey, Graphs Combin. 22(1) (2006) 1–35. Crossref, Web of Science, Google Scholar
3. D. Bauer, H. Broersma and H. J. Veldman, Not every 2-tough graph is Hamiltonian, Discrete Appl. Math. 99(1) (2000) 317–321. Crossref, Web of Science, Google Scholar
4. D. Bauer, S. L. Hakimi and E. Schmeichel, Recognizing tough graphs is NP-hard, Discrete Appl. Math. 28(3) (1990) 191–195. Crossref, Web of Science, Google Scholar
5. J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, Vol. 244 (Springer, New York, 2008). Crossref, Google Scholar
6. H. Broersma, V. Patel and A. Pyatkin, On toughness and Hamiltonicity of $2 K_{2}$ -free graphs. J. Graph Theory 75(3) (2014) 244–255. Crossref, Web of Science, Google Scholar
7. V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Math. 5(3) (1973) 215–228. Crossref, Google Scholar
8. H. N. de Ridder et al., Information system on graph classes and their inclusions (ISGCI) (2015), http://www.graphclasses.org. Google Scholar
9. M. N. Ellingham and X. Zha, Toughness, trees, and walks, J. Graph Theory 33(3) (2000) 125–137. Crossref, Web of Science, Google Scholar
10. M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, Vol. 57, 2nd edn. (Elsevier Science B.V., Amsterdam, 2004). With a foreword by Claude Berge. Google Scholar
11. B. Jackson and N. C. Wormald, $k$ -walks of graphs, Australas. J. Combin. 2 (1990) 135–146. Google Scholar
12. T. Kaiser, Z. Ryjáček, D. Král, M. Rosenfeld and H.-J. Voss, Hamilton cycles in prisms, J. Graph Theory 56(4) (2007) 249–269. Crossref, Web of Science, Google Scholar
13. M. Kouider and P. D. Vestergaard, Connected factors in graphs—a survey, Graphs Combin. 21(1) (2005) 1–26. Crossref, Web of Science, Google Scholar
14. H. J. Veldman, Existence of dominating cycles and paths, Discrete Math. 43(2) (1983) 281–296. Crossref, Web of Science, Google Scholar