z-logo
open-access-imgOpen Access
Arc-disjoint Hamiltonian paths in strong round decomposable local tournaments
Author(s) -
Meng Wei
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2185
Subject(s) - mathematics , disjoint sets , combinatorics , arc (geometry) , hamiltonian (control theory) , hamiltonian path , discrete mathematics , geometry , mathematical optimization , graph
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom