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

DOI10.1142/S0218216516420116MaRDI QIDQ2835378zbMATH OpenOpenAlexWikidataFDO

Authors Gao Mou, Dmitrii V. Pasechnik

Publication date 2 December 2016

Published in Journal of Knot Theory and its Ramifications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.0514

zbMATH Keywords

\(k\)-walkprism-Hamiltonicity\(2K_2\)-free graphs\(t\)-tough graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

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 epsilon>0 every (1+epsilon)-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.

Recommendations

• Hamiltonian cycles in 3-tough \(2K_2\)-free graphs
• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs
• Toughness, trees, and walks

Cites work

• scientific article; zbMATH DE number 68918 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(3)

• Hamiltonian cycles in 2‐tough 2K2 $2{K}_{2}$‐free graphs
• Toughness and prism-Hamiltonicity of \(P_4\)-free graphs
• Spanning trails with maximum degree at most 4 in \(2K_2\)-free graphs

This page was built for publication: Edge-dominating cycles, \(k\)-walks and Hamilton prisms in \(2K_2\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835378)