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

Abstract

We show that an edge-dominating cycle in a $2K_2$-free graph can be found in polynomial time; this implies that every 1/(k-1)-tough $2K_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 (1990). Furthermore, we prove that for any ε>0 every (1+ε)-tough $2K_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.

LaTeX, 8 pages

Cited by in corpus (6)

• Nonempty intersection of longest paths in $2K_2$-free graphs
• Hamiltonian cycles in 3-tough $2K_2$-free graphs
• Spanning trails with maximum degree at most 4 in $2K_2$-free graphs
• Hamiltonian cycles in tough $(P_2\cup P_3)$-free graphs
• Toughness and spanning trees in $K_4$-minor-free graphs
• Hamiltonian prisms on 5-chordal graphs