Journal article
Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
- Abstract:
- We show that an edge-dominating cycle in a 2K2-free graph can be found in polynomial time; this implies that every 1k−1-tough 2K2-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 [k-walks of graphs, Australas. J. Combin.2 (1990) 135–146]. Furthermore, we prove that for any ϵ>0 every (1+ϵ)-tough 2K2-free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 85.3KB, Terms of use)
-
- Publisher copy:
- 10.1142/S0218216516420116
Authors
- Publisher:
- World Scientific Publishing
- Journal:
- Journal of Knot Theory and Its Ramifications More from this journal
- Volume:
- 25
- Issue:
- 12
- Article number:
- 1642011
- Publication date:
- 2016-09-27
- Acceptance date:
- 2015-12-11
- DOI:
- EISSN:
-
1793-6527
- ISSN:
-
0218-2165
- Keywords:
- Pubs id:
-
pubs:581032
- UUID:
-
uuid:5288eed1-87d4-4492-89e5-e878fc08dd93
- Local pid:
-
pubs:581032
- Source identifiers:
-
581032
- Deposit date:
-
2016-01-02
Terms of use
- Copyright holder:
- World Scientific
- Copyright date:
- 2016
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from World Scientific at: https://doi.org/10.1142/S0218216516420116
If you are the owner of this record, you can report an update to it here: Report update to this record