Geodesic
Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 477-490

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2018_38_2_a10,
     author = {Li, Ruijuan and Han, Tingting},
     title = {Arc-Disjoint {Hamiltonian} {Cycles} in {Round} {Decomposable} {Locally} {Semicomplete} {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {477--490},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a10/}
}
TY  - JOUR
AU  - Li, Ruijuan
AU  - Han, Tingting
TI  - Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 477
EP  - 490
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a10/
LA  - en
ID  - DMGT_2018_38_2_a10
ER  - 
%0 Journal Article
%A Li, Ruijuan
%A Han, Tingting
%T Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 477-490
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a10/
%G en
%F DMGT_2018_38_2_a10
Li, Ruijuan; Han, Tingting. Arc-Disjoint Hamiltonian Cycles in Round Decomposable Locally Semicomplete Digraphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 477-490. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a10/