Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
Pasechnik, Dmitrii V.
Date of Issue2016
School of Physical and Mathematical Sciences
We show that an edge-dominating cycle in a 2K22K2-free graph can be found in polynomial time; this implies that every 1k−11k−1-tough 2K22K2-free graph admits a kk-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 [kk-walks of graphs, Australas. J. Combin. 2 (1990) 135–146]. Furthermore, we prove that for any ϵ>0ϵ>0 every (1+ϵ)(1+ϵ)-tough 2K22K2-free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.
Journal of Knot Theory and Its Ramifications
© 2016 World Scientific Publishing Company. This is the author created version of a work that has been peer reviewed and accepted for publication by Journal of Knot Theory and Its Ramifications, World Scientific Publishing Company. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1142/S0218216516420116].