Hamilton cycles in the union of random permutations

DOI<83::AID-RSA6>3.0.CO;2-I 10.1002/1098-2418(200101)18:1<83::AID-RSA6>3.0.CO;2-IzbMath0968.05048MaRDI QIDQ4761359

Alan M. Frieze

Publication date: 4 September 2001

Full work available at URL: https://doi.org/10.1002/1098-2418(200101)18:1<83::aid-rsa6>3.0.co;2-i

zbMATH Keywords

Hamilton cycle; random permutations

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

05C45: Eulerian and Hamiltonian graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Almost all regular graphs are Hamiltonian
• Hamiltonian cycles in random regular graphs
• Finding Hamilton cycles in sparse random graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The asymptotic number of labeled graphs with given degree sequences
• Hamilton cycles in a class of random directed graphs
• Asymptotic enumeration by degree sequence of graphs of high degree
• Almost all cubic graphs are Hamiltonian
• Almost all regular graphs are hamiltonian
• Hamilton Cycles in Random Regular Digraphs
• When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Generating and Counting Hamilton Cycles in Random Regular Graphs