\(k\)-Ordered Hamilton cycles in digraphs (Q958680)

From MaRDI portal
scientific article
Language Label Description Also known as
English
\(k\)-Ordered Hamilton cycles in digraphs
scientific article

    Statements

    \(k\)-Ordered Hamilton cycles in digraphs (English)
    0 references
    0 references
    8 December 2008
    0 references
    Given a digraph \(D\), let \(\delta^0(D)=\min\{\delta^+(D),\delta^-(D)\}\) be the minimum semi-degree. \(D\) is \(k\)-ordered Hamiltonian if for every sequence \(s_1,\dots,s_k\) of distinct vertices of \(D\) there is a Hamiltonian cycle which encounters \(s_1,\dots,s_k\) in this order. In the paper it is proved that every digraph \(D\) of sufficiently large order \(n\) with \(\delta^0(D)\geq\lceil(n+k)/2\rceil-1\) is \(k\)-ordered Hamiltonian. The bound on the minimum semi-degree is best possible and the proof shows that it suffices to take \(n\geq ck^9\) for a constant \(c\).
    0 references
    0 references
    Hamiltonian cycle
    0 references
    directed graph
    0 references
    ordered cycle
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references