Authors:
W. Meng
Title:
Arc-disjoint Hamiltonian paths in strong round decomposable local tournaments
Source:
Discussiones Mathematicae Graph Theory
Received 30.11.2017, Revised 29.10.2018, Accepted 29.10.2018, doi: 10.7151/dmgt.2185

Abstract:
Thomassen \cite{to} proved that every strong tournament has a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices if and only if it is not an almost transitive tournament of odd order. As a subclass of local tournaments, Li et al. \cite{li1} confirmed the existence of such two paths in 2-strong round decomposable local tournaments. In this paper, we show that every strong, but not 2-strong, round decomposable local tournament contains a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices except for three classes of digraphs. Thus Thomassen's result is partly extended to round decomposable local tournaments. In addition, we also characterize strong round digraphs which contain a pair of arc-disjoint Hamiltonian paths with distinct initial vertices and distinct terminal vertices.
Keywords:
local tournament, round-decomposable, arc-disjoint Hamiltonian paths

Links:
PDF