We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Edge-dominating cycles, -walks and Hamilton prisms in -free graphs.
- Authors
Mou, Gao; Pasechnik, Dmitrii V.
- Abstract
We show that an edge-dominating cycle in a -free graph can be found in polynomial time; this implies that every -tough -free graph admits a -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 [-walks of graphs, Australas. J. Combin. 2 (1990) 135-146]. Furthermore, we prove that for any every -tough -free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.
- Subjects
GRAPH theory; POLYNOMIAL time algorithms; SET theory; HAMILTONIAN graph theory; NP-hard problems
- Publication
Journal of Knot Theory & Its Ramifications, 2016, Vol 25, Issue 12, p-1
- ISSN
0218-2165
- Publication type
Article
- DOI
10.1142/S0218216516420116