首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 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 u1,u2,,un (i.e., uiuj for all 1i<jn) by reversing the arc u1un. 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.
Keywords:Local tournament  Semicomplete decomposition  Arc-disjoint  Hamiltonian path  Hamiltonian cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号