Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
Copyright policy )Edge-dominating cycles, k-walks and Hamilton prisms in 2K2-free graphs
We show that an edge-dominating cycle in a [Formula: see text]-free graph can be found in polynomial time; this implies that every [Formula: see text]-tough [Formula: see text]-free graph admits a [Formula: see text]-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 [[Formula: see text]-walks of graphs, Australas. J. Combin. 2 (1990) 135–146]. Furthermore, we prove that for any [Formula: see text] every [Formula: see text]-tough [Formula: see text]-free graph is prism-Hamiltonian and give an effective construction of a Hamiltonian cycle in the corresponding prism, along with few other similar results.
- University of Oxford United Kingdom
- Nanyang Technological University Singapore
Eulerian and Hamiltonian graphs, 2K2-free graphs, \(t\)-tough graphs, \(k\)-walk, prism-Hamiltonicity, \(2K_2\)-free graphs, 004, 510, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), FOS: Mathematics, t-tough graphs, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles
Eulerian and Hamiltonian graphs, 2K2-free graphs, \(t\)-tough graphs, \(k\)-walk, prism-Hamiltonicity, \(2K_2\)-free graphs, 004, 510, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Graph algorithms (graph-theoretic aspects), FOS: Mathematics, t-tough graphs, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!