Abstract | ||
---|---|---|
In 1986, Thomassen posed the following conjecture: every 4-connected line graph has a Hamiltonian cycle. As a possible approach to the conjecture, many researchers have considered statements that are equivalent or related to it. One of them is the conjecture by Bondy: there exists a constant c(0) with 0 < c(0) <= 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 implies Bondy's conjecture, but nothing about the converse has been shown. 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1137/130937974 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
Hamiltonian cycles,line graphs,Thomassen's conjecture,dominating cycles,Bondy's conjecture | Discrete mathematics,Combinatorics,abc conjecture,Line graph,Hamiltonian path,Cubic graph,Elliott–Halberstam conjecture,Lonely runner conjecture,Conjecture,Collatz conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 1 | 0895-4801 |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Roman Cada | 1 | 40 | 8.35 |
Shuya Chiba | 2 | 35 | 12.93 |
Kenta Ozeki | 3 | 138 | 36.31 |
Petr Vrána | 4 | 96 | 12.89 |
Kiyoshi Yoshimoto | 5 | 133 | 22.65 |