DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

W. Meng

Title:

Arc-disjoint Hamiltonian paths in strong round decomposable local tournaments

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-11-30, Revised: 2018-10-29, Accepted: 2018-10-29, https://doi.org/10.7151/dmgt.2185

Abstract:

Thomassen \cite{to} 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. \cite{li1} 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

PDF
Close