Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
Gao Mou, Dmitrii V. Ṗasechnik · Journal of Knot Theory and Its Ramifications · 2016
We show that an edge-dominating cycle in a [Formula: see text]-free graph can be found in polynomial time; this implies that every [Formula: see text]-tough [Formula: see text]-free graph admits a [Formula: see text]-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 [[Formula: see text]-walks of graphs, Australas. J. Combin. 2 (1990) 135–146]. Furthermore, we prove that for any [Formula: see text] every [Formula: see text]-tough [Formula: see text]-free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.