Hamiltonian paths containing a given arc, in almost regular bipartite tournaments (Q1877685): Difference between revisions

A multipartite tournament is an orientation of a complete multipartite graph. A directed graph \(D\) is regular, if for some \(k\), \(d^+(x) = d^-(x) = k\) for all \(x \in V(D)\). \(D\) is almost regular, if each of \(d^+(x)\), \(d^-(x)\) is \(k\) or \(k+1\) for all \(x \in V(D)\). \textit{D. Amar} and \textit{Y. Manoussakis} [J. Comb. Theory, Ser. B 50, No. 2, 254-264 (1990; Zbl 0712.05031)] and \textit{J. Wang} [Ars Comb. 32, 279-284 (1991; Zbl 0759.05056)] proved that every arc of a regular bipartite tournament is contained in a Hamiltonian cycle. Extending their result, the author proved that if \(T\) is an almost regular bipartite tournament with partite sets \(X\), \(Y\), then every arc of \(T\) is contained in a Hamiltonian path if and only if \(T\) is not isomorphic to \(T_{3,3}\), an almost regular bipartite tournament presented in the paper, and \(| | X| - | Y| | \leq 1\). As a corollary of this result and results by \textit{L. Volkmann} and \textit{A. Yeo} [Discrete Math. 281, No. 1--3, 267--276 (2004; Zbl 1050.05061)] and \textit{O. S. Jakobsen}, [Cycles and paths in tournaments (Ph.D. Thesis, University of Aarhus, 1972)], the author also proved that if \(D\) is an almost regular multipartite tournament with partite sets of equal size, then every arc of \(D\) is contained in a Hamiltonian path if and only if \(D\) is not isomorphic to \(T_{3,3}\).