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

From MaRDI portal
Revision as of 11:53, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Hamiltonian paths containing a given arc, in almost regular bipartite tournaments
scientific article

    Statements

    Hamiltonian paths containing a given arc, in almost regular bipartite tournaments (English)
    0 references
    0 references
    19 August 2004
    0 references
    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}\).
    0 references
    0 references
    Hamiltonian paths
    0 references
    bipartite tournaments
    0 references
    almost regular bipartite tournaments
    0 references
    almost regular multipartite tournaments
    0 references

    Identifiers