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/

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics, Spring-Verlag, London, 2009). doi:10.1007/978-1-84800-998-1

[2] J. Bang-Jensen, Locally semicomplete digraph: A generalization of tournaments, J. Graph Theory 14 (1990) 371–390. doi:10.1002/jgt.3190140310

[3] J. Bang-Jensen, Y. Guo, G. Gutin and L. Volkmann, A classification of locally semicomplete digraphs, Discrete Math. 167-168 (1997) 101–114. doi:10.1016/S0012-365X(96)00219-1

[4] J. Bang-Jensen and J. Huang, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, J. Combin. Theory Ser. B 102 (2012) 701–714. doi:10.1016/j.jctb.2011.09.001

[5] Y. Guo, Locally Semicomplete Digraphs (Ph.D. Thesis, RWTH Aachen University, 1995).

[6] Y. Guo, Strongly Hamiltonian-connected locally semicomplet digraphs, J. Graph Theory 21 (1996) 65–73. doi:10.1002/(SICI)1097-0118(199605)22:1h65::AID-JGT9i3.0.CO;2-J

[7] F. Harary and L. Moser, The theory of round robin tournaments, Amer. Math. Monthly 73 (1966) 231–246. doi:10.2307/2315334

[8] J. Huang, On the structure of local tournaments, J. Combin. Theory Ser. B 63 (1995) 200–221. doi:10.1006/jctb.1995.1016

[9] S. Li, W. Meng, Y. Guo and G. Xu, A local tournament contains a vertex whose out-arc are pseudo-girth-pancyclic, J. Graph Theory 62 (2009) 346–361. doi:10.1002/jgt.20404

[10] D. Meierling, Local tournaments with the minimum number of Hamiltonian cycles or cycles of length three, Discrete Math. 310 (2010) 1940–1948. doi:10.1016/j.disc.2010.03.003

[11] C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in tournaments, Proc. Lond. Math. Soc. (3) 45 (1982) 151–168. doi:10.1112/plms/s3-45.1.151

[12] R. Wang, A. Yang and S. Wang, Kings in locally semicomplete digraphs, J. Graph Theory 63 (2010) 279–283. doi:10.1002/jgt.20426

[13] X.H. Zhang, R.J. Li and S.J. Li, H-force sets of locally semicomplete digraphs, Discrete Appl. Math. 160 (2012) 2491–2496. doi:10.1016/j.dam.2012.06.014