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

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...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριοι συγγραφείς: Mou, Gao, Pasechnik, Dmitrii V.
Άλλοι συγγραφείς: School of Physical and Mathematical Sciences
Μορφή: Journal Article
Γλώσσα:English
Έκδοση: 2017
Θέματα:
Διαθέσιμο Online:https://hdl.handle.net/10356/83360
http://hdl.handle.net/10220/42557
Περιγραφή
Περίληψη: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.