Hamiltonian paths containing a given arc, in almost regular bipartite tournaments

A tournament is an orientation of a complete graph, and in general a multipartite or c-partite tournament is an orientation of a complete c-partite graph. If x is a vertex of a digraph D, then we denote by d(+)(x) and d(-)(x) the outdegree and indegree of x, respectively. The global irregularity of a digraph D is defined by i(g)(D) = max{d(+)(x),d(-)(x)} - min {d(+)(y),d(-)(y)} over all vertices x and y of D (including x = y). If i(g)(D) greater than or equal to 1, then D is called almost regular, and if i(g)(D) = 0, then D is regular. More than 10 years ago, Amar and Manoussakis and independently Wang proved that every arc of a regular bipartite tournament is contained in a directed Hamiltonian cycle. In this paper, we prove that every arc of an almost regular bipartite tournament T is contained in a directed Hamiltonian path if and only if the cardinalities of the partite sets differ by at most one and T is not isomorphic to T-3,T-3, where T-3,T-3 is an almost regular bipartite tournament with three vertices in each partite set. As an application of this theorem and other results, we show that every arc of an almost regular c-partite tournament D with the partite sets V-1, V-2,...,V-c such that \V\ = \V-2\ =...= \V-c\, is contained in a directed Hamiltonian path if and only if D is not isomorphic to T-3,T-3. (C) 2004 Elsevier B.V. All rights reserved.