Lo, A;
Patel, V;
Skokan, J;
Talbot, J;
(2017)
Decomposing tournaments into paths.
Electronic Notes in Discrete Mathematics
, 61
pp. 813-818.
10.1016/j.endm.2017.07.040.
Preview |
Text
template.pdf - Accepted Version Download (241kB) | Preview |
Abstract
In this work we consider a generalisation of Kelly's conjecture which is due 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 concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.
Type: | Article |
---|---|
Title: | Decomposing tournaments into paths |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1016/j.endm.2017.07.040 |
Publisher version: | https://doi.org/10.1016/j.endm.2017.07.040 |
Language: | English |
Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
Keywords: | tournaments, decomposition, paths |
UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
URI: | https://discovery.ucl.ac.uk/id/eprint/10045844 |
Archive Staff Only
View Item |