Path and cycle decompositions of dense graphs

• Verfasst von: Girao, Antonio [VerfasserIn]
• Verfasst von: Granet, Bertille [VerfasserIn]
• Verfasst von: Kühn, Daniela [VerfasserIn]
• Verfasst von: Osthus, Deryk [VerfasserIn]
• Titel: Path and cycle decompositions of dense graphs
• Verf.angabe: António Girão, Bertille Granet, Daniela Kühn and Deryk Osthus
• E-Jahr: 2021
• Jahr: 15 May 2021
• Umfang: 50 S.
• Fussnoten: Gesehen am 28.11.2022
• Titel Quelle: Enthalten in: London Mathematical SocietyJournal of the London Mathematical Society
• Ort Quelle: Oxford : Wiley, 1926
• Jahr Quelle: 2021
• Band/Heft Quelle: 104(2021), 3, Seite 1085-1134
• ISSN Quelle: 1469-7750
• DOI: doi:10.1112/jlms.12455
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: 05C38
• Sach-SW: 05C70
• Sach-SW: 05D40 (primary)
• K10plus-PPN: 1823726186
• K10plus-PPN:
  Universitätsbibliothek
• Lokale URL UB: Zum Volltext

Abstract

We make progress on three long standing conjectures from the 1960s about path and cycle decompositions of graphs. Gallai conjectured that any connected graph on n vertices can be decomposed into at most ⌈n2⌉ paths, while a conjecture of Hajós states that any Eulerian graph on n vertices can be decomposed into at most ⌊n−12⌋ cycles. The Erdős-Gallai conjecture states that any graph on n vertices can be decomposed into O(n) cycles and edges. We show that if G is a sufficiently large graph on n vertices with linear minimum degree, then the following hold. (i)G can be decomposed into at most n2+o(n) paths. (ii)If G is Eulerian, then it can be decomposed into at most n2+o(n) cycles. (iii)G can be decomposed into at most 3n2+o(n) cycles and edges. If in addition G satisfies a weak expansion property, we asymptotically determine the required number of paths/cycles for each such G. (iv)G can be decomposed into maxodd(G)2,Δ(G)2+o(n) paths, where odd(G) is the number of odd-degree vertices of G. (v)If G is Eulerian, then it can be decomposed into Δ(G)2+o(n) cycles. All bounds in (i)-(v) are asymptotically best possible.