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

Kód výsledku v IS VaVaI

RIV/49777513:23520/15:43924805 - isvavai.cz

Výsledek na webu

http://epubs.siam.org/doi/10.1137/130937974

DOI - Digital Object Identifier

10.1137/130937974

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM JOURNAL ON DISCRETE MATHEMATICS

ISSN

0895-4801

e-ISSN

—

Svazek periodika

29

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

10

Strana od-do

26-35

Kód UT WoS článku

000352224600002

EID výsledku v databázi Scopus

—