Arc-disjoint hamiltonian paths in non-round decomposable local tournaments |
| |
Authors: | Ruijuan Li Tingting Han |
| |
Institution: | School of Mathematical Sciences, Shanxi University, Taiyuan, Shanxi, 030006, PR China |
| |
Abstract: | Thomassen proved that a strong tournament has a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices if and only if is not an almost transitive tournament of odd order, where an almost transitive tournament is obtained from a transitive tournament with acyclic ordering (i.e., for all ) by reversing the arc . A digraph is a local tournament if for every vertex of , both the out-neighbors and the in-neighbors of 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. |
| |
Keywords: | Local tournament Semicomplete decomposition Arc-disjoint Hamiltonian path Hamiltonian cycle |
本文献已被 ScienceDirect 等数据库收录! |
|