Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Charlotte Knierim, Maxime Larcher, Anders Martinsson +1

Hajós conjectured in 1968 that every Eulerian \(n\)-vertex graph can be decomposed into at most $\lfloor (n-1)/2\rfloor$ edge-disjoint cycles. This has been confirmed for some spec…