Přejít k obsahu


A Relationship Between Thomassen's Conjecture and Bondy's Conjecture

Citace:
ČADA, R., CHIBA, S., OZEKI, K., VRÁNA, P., YOSHIMOTO, K. A Relationship Between Thomassen's Conjecture and Bondy's Conjecture. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, roč. 29, č. 1, s. 26-35. ISSN: 0895-4801
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: A Relationship Between Thomassen's Conjecture and Bondy's Conjecture
Rok vydání: 2015
Autoři: Doc. Ing. Roman Čada Ph.D. , Shuya Chiba Ph.D. , Kenta Ozeki Ph.D. , Mgr. Petr Vrána Ph.D. , Prof. Kiyoshi Yoshimoto Ph.D.
Abstrakt CZ: Bondyho hypotéza říká, že existuje konstanta c_0, 0< c_0 \leq 1 taková, že každý cyklicky hranově 4-souvislý kubický graf H má kružnici s délkou alespoň c_0 |V(H)|. Je známo, že Thomessenova hypotéza (každý 4-souvislý hranový graf je hamiltonovský) implikuje Bondyho hypotézu. V článku je ukázáno, že Bondyho hypotéza implikuje slabší verzi Thomassenovy hypotézy: 4-souvislý hranový graf s minimálním stupněm alespoň 5 má Hamiltonovskou kružnici.
Abstrakt EN: A conjecture by Bondy says: there exists a constant c_0 with 0 < c_0 \leq 1 such that every cyclically 4-edge-connected cubic graph H has a cycle of length at least c_0 |V(H)|. It is known that Thomassen's conjecture (every 4-connected line graph is Hamiltonian) implies Bondy's conjecture. In this paper, we show that Bondy's conjecture implies a slightly weaker version of Thomassen's conjecture: every 4-connected line graph with minimum degree at least 5 has a Hamiltonian cycle.
Klíčová slova

Zpět

Patička