Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments.

*(English)*Zbl 1261.05053Summary: A long-standing conjecture of Kelly states that every regular tournament on \(n\) vertices can be decomposed into \((n-1)/2\) edge-disjoint Hamilton cycles. We prove this conjecture for large \(n\). In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs.

We show that every sufficiently large regular digraph \(G\) on \(n\) vertices whose degree is linear in \(n\) and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erdős on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of C. St. J. A. Nash-Williams [Lect. Notes Math. 186, 197–210 (1971; Zbl 0223.05122)].

We also apply our result to solve a problem on the domination ratio of the asymmetric travelling salesman problem, which was raised e.g. by F. Glover and A. P. Punnen [J. Oper. Res. Soc. 48, No. 5, 502-510 (1997; Zbl 0882.90124)] as well as N. Alon et al. [J. Algorithms 50, No. 1, 118–131 (2004; Zbl 1068.68175)].

We show that every sufficiently large regular digraph \(G\) on \(n\) vertices whose degree is linear in \(n\) and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erdős on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of C. St. J. A. Nash-Williams [Lect. Notes Math. 186, 197–210 (1971; Zbl 0223.05122)].

We also apply our result to solve a problem on the domination ratio of the asymmetric travelling salesman problem, which was raised e.g. by F. Glover and A. P. Punnen [J. Oper. Res. Soc. 48, No. 5, 502-510 (1997; Zbl 0882.90124)] as well as N. Alon et al. [J. Algorithms 50, No. 1, 118–131 (2004; Zbl 1068.68175)].

##### MSC:

05C45 | Eulerian and Hamiltonian graphs |

05C20 | Directed graphs (digraphs), tournaments |

90C35 | Programming involving graphs or networks |