|
Citation:
|
KUŽEL, R., RYJÁČEK, Z., VRÁNA, P. Thomassen?s Conjecture Implies Polynomiality of 1-Hamilton-Connectedness in Line Graphs. Journal of Graph Theory, 2012, roč. 69, č. 3, s. 241-250. ISSN: 0364-9024
|
|
Type:
|
ČLÁNEK
|
|
Language:
|
eng
|
|
English title:
|
Thomassen?s Conjecture Implies Polynomiality of 1-Hamilton-Connectedness in Line Graphs
|
|
Publication year:
|
2012
|
|
Publication place:
|
Hoboken, NJ
|
|
Publisher name:
|
Wiley
|
|
Authors:
|
Prof. RNDr. Zdeněk Ryjáček DrSc.
,
Mgr. Petr Vrána
,
Ing. Roman Kužel Ph.D.
|
|
Abstract CZ:
|
Graf G je 1-hamiltonovsky souvislý jestliže G?x je hamiltonovsky souvislý pro každý uzel x. V článku dokazujeme, že Thomassenova hypotéza (každý 4-souvislý hranový graf je hamiltonovský, nebo, ekvivalentně, každý snark má dominantní kružnici) je ekvivalenní s tvrzením, že každý 4-souvislý hranový graf je 1-hamiltonovsky souvislý. Jako důsledek dostáváme tvrzení, že Thomassenova hypotéza implikuje polynomialitu 1-hamiltonovské souvislosti v hranových grafech. Důkaz NP-úplnosti 1-hamiltonovské souvislosti v hranových grafech by tedy znamenal, že buďto Thomassenova hypotéza neplatí, nebo P=NP.
|
|
Abstract EN:
|
A graph G is 1-Hamilton-connected if G?x is Hamilton-connected for every vertex x. 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 statement that every 4-connected line graph is 1-Hamilton-connected. As a corollary, we obtain that Thomassen?s conjecture implies polynomiality of 1-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
|
|
Keywords
|
|