06045735

j

06045735 Ku\v{z}el, Roman Ryj\'a\v{c}ek, Zden\v{e}k Vr\'ana, Petr Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs. J. Graph Theory 69, No. 3-4, 241-250 (2012). 2012 John Wiley \& Sons, New York, NY EN line graph 4-connected Hamiltonian Hamilton-connected dominating cycle Thomassen's conjecture snark

doi:10.1002/jgt.20578

Summary: A graph G is 1-Hamilton-connected if $G - x$ is Hamilton-connected for every x$\in 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\subset E^{+}(G) = \{xy| x, y\in V(G)\}$ with $1\leq |X|\leq 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$.