Authors:
T. Han, R. Li
Title:
Arc-disjont Hamiltonian cycles in round decomposable locally semicomplete digraphs
Source:
Discussiones Mathematicae Graph Theory
Received 17.08.2016, Revised 01.11.2016, Accepted 23.12.2016, doi: 10.7151/dmgt.2023

Abstract:
Let D=(V,A) be a digraph; if there is at least one arc between every pair of distinct vertices of D, then D is a semicomplete digraph. A digraph D is locally semicomplete if for every vertex x, the out-neighbours of x induce a semicomplete digraph and the in-neighbours of x induce a semicomplete digraph. A locally semicomplete digraph without 2-cycle is a local tournament. In 2012, Bang-Jensen and Huang [J. Combin Theory Ser. B 102 (2012) 701--714] concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs, and proposed the conjecture that every 3-strong local tournament has two arc-disjoint {Hamiltonian} cycles. According to Bang-Jensen, Guo, Gutin and Volkmann, locally semicomplete digraphs have three subclasses: the round decomposable; the non-round decomposable which are not semicomplete; the non-round decomposable which are semicomplete. In this paper, we prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint {Hamiltonian} cycles, which implies that the conjecture holds for the round decomposable local tournaments. Also, we characterize the 2-strong round decomposable local tournaments each of which contains a {Hamiltonian} path P and a {Hamiltonian} cycle arc-disjoint from P.
Keywords:
locally semicomplete digraph, local tournament, round decomposable, arc-disjoint, Hamiltonian cycle, Hamiltonian path

Links:
PDF