Leaf-to-leaf paths and cycles in degree-critical graphs
Combinatorica · 2026-04 · 46 (2)
DOI: 10.1007/s00493-026-00205-2 ↗Kurz gefasst
Fachartikel in der Zeitschrift Combinatorica, online erschienen am 04.03.2026. Verfasst von Francesco Di Braccio und 4 weiteren Autor:innen. Die Arbeit nennt 22 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
An n -vertex graph is degree 3-critical if it has $$2n - 2$$ 2 n - 2 edges and no proper induced subgraph with minimum degree at least 3. In 1988, Erdős, Faudree, Gyárfás, and Schelp asked whether one can always find cycles of all short lengths in these graphs, which was disproven by Narins, Pokrovskiy, and Szabó through a construction based on leaf-to-leaf paths in trees whose vertices have degree either 1 or 3. They went on to suggest several weaker conjectures about cycle lengths in degree 3-critical graphs and leaf-to-leaf path lengths in these so-called 1-3 trees. We resolve three of their questions either fully or up to a constant factor. Our main results are the following: every n -vertex degree 3-critical graph has $$\Omega (\log n)$$ Ω ( log n ) distinct cycle lengths; every tree with maximum degree $$\Delta \ge 3$$ Δ ≥ 3 and $$\ell $$ ℓ leaves has at least $$\log _{\Delta -1}\, ((\Delta -2)\ell )$$ log Δ - 1 ( ( Δ - 2 ) ℓ ) distinct leaf-to-leaf path lengths; for every integer $$N\ge 1$$ N ≥ 1 , there exist arbitrarily large 1–3 trees which have $$O(N^{0.91})$$ O ( N 0.91 ) distinct leaf-to-leaf path lengths smaller than N , and, conversely, every 1–3 tree on at least $$2^N$$ 2 N vertices has $$\Omega (N^{2/3})$$ Ω ( N 2 / 3 ) distinct leaf-to-leaf path lengths smaller than N . Several of our proofs rely on purely combinatorial means, while others exploit a connection to an additive problem that might be of independent interest.
Zitieren
APA
Braccio, F. D., Katsamaktsis, K., Ma, J., Malekshahian, A., & Zhao, Z. (2026). Leaf-to-leaf paths and cycles in degree-critical graphs. Combinatorica, 46(2). https://doi.org/10.1007/s00493-026-00205-2
Vancouver
Braccio FD, Katsamaktsis K, Ma J, Malekshahian A, Zhao Z. Leaf-to-leaf paths and cycles in degree-critical graphs. Combinatorica. 2026;46(2). doi:10.1007/s00493-026-00205-2
BibTeX
@article{Braccio2026,
author = {Braccio, Francesco Di and Katsamaktsis, Kyriakos and Ma, Jie and Malekshahian, Alexandru and Zhao, Ziyuan},
title = {Leaf-to-leaf paths and cycles in degree-critical graphs},
journal = {Combinatorica},
year = {2026},
volume = {46},
number = {2},
doi = {10.1007/s00493-026-00205-2}
}
EUVIMED