Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
✍ Scribed by Roman Kužel; Zdeněk Ryjáček; Petr Vrána
- Publisher
- John Wiley and Sons
- Year
- 2011
- Tongue
- English
- Weight
- 158 KB
- Volume
- 69
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A graph G is 1‐Hamilton‐connected if G−x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X⊂E^+^(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012