Please use this identifier to cite or link to this item:
Title: Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
Authors: Mou, Gao
Pasechnik, Dmitrii V.
Keywords: 2K2-free graphs
t-tough graphs
Issue Date: 2016
Source: Mou, G., & Pasechnik, D. V. (2016). Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs. Journal of Knot Theory and Its Ramifications, 25(12), 1642011-.
Series/Report no.: Journal of Knot Theory and Its Ramifications
Abstract: 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.
ISSN: 0218-2165
DOI: 10.1142/S0218216516420116
Schools: School of Physical and Mathematical Sciences 
Rights: © 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: [].
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Edge-dominating cycles, kk-walks and Hamilton prisms in 2K22K2-free graphs.pdf101.44 kBAdobe PDFThumbnail

Citations 50

Updated on Sep 25, 2023

Page view(s)

Updated on Sep 23, 2023

Download(s) 50

Updated on Sep 23, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.