Arc-disjoint hamiltonian paths in non-round decomposable local tournaments

作者：Li, Ruijuan^*; Han, Tingting

来源：Discrete Mathematics, 2017, 340(12): 2916-2924.

DOI：10.1016/j.disc.2017.07.024

• Local tournament
• Semicomplete decomposition
• Arc-disjoint
• Hamiltonian path
• Hamiltonian cycle

Thomassen proved that a strong tournament T has a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices if and only if T is not an almost transitive tournament of odd order, where an almost transitive tournament is obtained from a transitive tournament with acyclic ordering u(1), u(2), ... , u(n), (i.e., u(i) -> u(j) for all 1 <= i < j <= n) by reversing the arc u(1)u(n). A digraph D is a local tournament if for every vertex x of D, both the out-neighbors and the in-neighbors of x induce tournaments. Bang Jensen, Guo, Gutin and Volkmann split local tournaments into three subclasses: the round decomposable; the non-round decomposable which are not tournaments; the non round decomposable which are tournaments. In 2015, we proved that every 2-strong round decomposable local tournament has a Hamiltonian path and a Hamiltonian cycle which are arc-disjoint if and only if it is not the second power of an even cycle. In this paper, we discuss the arc-disjoint Hamiltonian paths in non-round decomposable local tournaments, and prove that every 2-strong non-round decomposable local tournament contains a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices. This result combining with the one on round decomposable local tournaments extends the above-mentioned result of Thomassen to 2-strong local tournaments.

• 出版日期2017-12
• 单位山西大学