Decomposing tournaments into paths

Open Access
Authors
Publication date 08-2020
Journal Proceedings of the London Mathematical Society
Volume | Issue number 121 | 2
Pages (from-to) 426-461
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
Abstract
We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament (Formula presented.). There is a natural lower bound for this number in terms of the degree sequence of (Formula presented.) and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.
Document type Article
Language English
Published at https://doi.org/10.1112/plms.12328
Other links https://www.scopus.com/pages/publications/85089366470
Downloads
Decomposing tournaments into paths (Final published version)
Permalink to this page
Back