Hamilton cycles in a class of random directed graphs (Q1333332)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Hamilton cycles in a class of random directed graphs
scientific article

    Statements

    Hamilton cycles in a class of random directed graphs (English)
    0 references
    13 September 1994
    0 references
    This paper is the latest in a long line investigating thresholds for a random graph or digraph to have a Hamiltonian cycle. The random digraph \(D_{k- in,l-out}\) is defined as follows: it has vertices \(1,2,\dots, n\), and each vertex \(v\) chooses, independently and uniformly at random, \(k\) arcs \(xv\) and \(l\) arcs \(vy\). It is shown that, with probability tending to 1 as \(n\to \infty\), the random digraph \(D_{3- in,3-out}\) is Hamiltonian. [The quest continues to show that \(D_{2- in,2-out}\) is Hamiltonian.] The idea of the proof is to consider \(D_{3-in,3-out}\) as the union of two random digraphs \(D_ a\) and \(D_ b\); observe from previous results that in \(D_ a\) there is usually a permutation digraph with not too many cycles; use arcs from \(D_ b\) to try to increase the minimum cycle length; and finally to cut up these long cycles and try to rejoin them to form a Hamiltonian cycle, again using arcs of \(D_ b\).
    0 references
    thresholds
    0 references
    random graph
    0 references
    digraph
    0 references
    Hamiltonian cycle
    0 references
    random digraph
    0 references
    0 references
    0 references

    Identifiers

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