Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs

© 2016 World Scientific Publishing Company.We show that an edge-dominating cycle in a 2K2-free graph can be found in polynomial time; this implies that every 1 k-1-tough 2K2-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 2K2-free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.