Narins, L;
Pokrovskiy, A;
Szabo, T;
(2017)
Graphs without proper subgraphs of minimum degree 3 and short cycles.
Combinatorica
, 37
pp. 495-519.
10.1007/s00493-015-3310-9.
Preview |
Text
CyclesPaper.pdf - Accepted Version Download (308kB) | Preview |
Abstract
We study graphs on n vertices which have 2n−2 edges and no proper induced subgraphs of minimum degree 3. Erdős, Faudree, Gyárfás, and Schelp conjectured that such graphs always have cycles of lengths 3,4,5,...,C(n) for some function C(n) tending to in finity. We disprove this conjecture, resolve a related problem about leaf-to-leaf path lengths in trees, and characterize graphs with n vertices and 2n−2 edges, containing no proper subgraph of minimum degree 3.
| Type: | Article |
|---|---|
| Title: | Graphs without proper subgraphs of minimum degree 3 and short cycles |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s00493-015-3310-9 |
| Publisher version: | https://doi.org/10.1007/s00493-015-3310-9 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10112658 |
Archive Staff Only
 |
View Item |
