Premium
Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs
Author(s) -
Kužel Roman,
Ryjáček Zdeněk,
Vrána Petr
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20578
Subject(s) - social connectedness , mathematics , combinatorics , conjecture , hamiltonian path , graph , corollary , hamiltonian (control theory) , discrete mathematics , psychology , mathematical optimization , psychotherapist
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