Path decompositions of tournaments

Abstract

In 1976, Alspach, Mason, and Pullman conjectured that any tournament $T$ of even order can be decomposed into exactly $\mathrm{ex}(T)$ paths, where $\mathrm{ex}(T):=\frac{1}{2}{\sum }_{v\in V(T)}|d_T^{+}(v)-d_T^{-}(v)|$. We prove this conjecture for all sufficiently large tournaments. We also prove an asymptotically optimal result for tournaments of odd order.

73 pages, 2 figures; final version, to appear in the Proceedings of the London Mathematical Society

Cited by in corpus (1)

• Transitive path decompositions of Cartesian products of complete graphs