Geodesic
Arc-Disjoint Hamiltonian Paths in Strong Round Decomposable Local Tournaments
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 297-310.

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

Thomassen, [Edge-disjoint Hamiltonian paths and cycles in tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163] 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. [Arc-disjoint Hamiltonian cycles in round decomposable local tournaments, Discuss. Math. Graph Theory 38 (2018) 477–490] 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 
@article{DMGT_2021_41_1_a18,
     author = {Meng, Wei},
     title = {Arc-Disjoint {Hamiltonian} {Paths} in {Strong} {Round} {Decomposable} {Local} {Tournaments}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {297--310},
     publisher = {mathdoc},
     volume = {41},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a18/}
}
TY  - JOUR
AU  - Meng, Wei
TI  - Arc-Disjoint Hamiltonian Paths in Strong Round Decomposable Local Tournaments
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 297
EP  - 310
VL  - 41
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a18/
LA  - en
ID  - DMGT_2021_41_1_a18
ER  - 
%0 Journal Article
%A Meng, Wei
%T Arc-Disjoint Hamiltonian Paths in Strong Round Decomposable Local Tournaments
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 297-310
%V 41
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a18/
%G en
%F DMGT_2021_41_1_a18
Meng, Wei. Arc-Disjoint Hamiltonian Paths in Strong Round Decomposable Local Tournaments. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 297-310. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a18/

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

[2] 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

[3] J. Bang-Jensen and G. Gutin, Classes of Directed Graphs (Springer Monographs in Mathematics, 2018). doi: 10.1007/978-3-319-71840-8

[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, Germany, 1995).

[6] R. Li and T. Han, Arc-disjoint Hamiltonian paths in non-round decomposable local tournaments, Discrete Math. 340 (2017) 2916–2924. doi: 10.1016/j.disc.2017.07.024

[7] R. Li and T. Han, Arc-disjoint Hamiltonian cycles in round decomposable local tournaments, Discuss. Math. Graph Theory 38 (2018) 477–490. doi: 10.7151/dmgt.2023

[8] 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

[9] W. Meng, J. Guo, M. Lu, Y. Guo and L. Volkmann, Universal arcs in local tournaments, Discrete Math. 340 (2017) 2900–2915. doi: 10.1016/j.disc.2017.07.025

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

[11] C. Thomassen, Edge-disjoint Hamiltonian paths and cycles in tournaments, J. Combin. Theory Ser. B 28 (1980) 142–163. doi: 10.1016/0095-8956(80)90061-1

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