Hamilton Cycles in Random Regular Digraphs

DOI10.1017/S096354830000095XzbMath0809.05081OpenAlexW2055286719MaRDI QIDQ4306430

Colin Cooper, Alan M. Frieze, Michael S. O. Molloy

Publication date: 24 October 1994

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s096354830000095x

zbMATH Keywords

digraphHamilton cyclesoutdegreesrandom regular digraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items

On the 2‐cyclic property in 2‐regular digraphs, An improved fully polynomial randomized approximation scheme (FPRAS) for counting the number of Hamiltonian cycles in dense digraphs, The birth of the strong components, Random Regular Graphs: Asymptotic Distributions and Contiguity, Unnamed Item, The component counts of random injections, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Hamilton cycles in the union of random permutations, Linear arboricity of regular digraphs, Random dense bipartite graphs and directed graphs with specified degrees

Cites Work

• Almost all regular graphs are Hamiltonian
• Hamiltonian cycles in random regular graphs
• Finding Hamilton cycles in sparse random graphs
• The asymptotic number of labeled graphs with given degree sequences
• Almost all cubic graphs are Hamiltonian