On the Number of Hamilton Cycles in Sparse Random Graphs
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
Abstract: We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Recommendations
- On the number of hamilton cycles in a random graph
- Counting Hamilton cycles in sparse random directed graphs
- Finding Hamilton cycles in sparse random graphs
- On the number of Hamilton cycles in pseudo-random graphs
- scientific article; zbMATH DE number 4087714
- scientific article; zbMATH DE number 4193709
- Hamiltonian cycles in random regular graphs
- On two Hamilton cycle problems in random graphs
- Counting the Number of Hamilton Cycles in Random Digraphs
Cited in
(38)- Limit distribution for the existence of Hamiltonian cycles in a random graph
- Finding Hamilton cycles in sparse random graphs
- The number of Hamiltonian decompositions of regular graphs
- Hamilton cycles in sparse locally connected graphs
- Bounding the number of cycles in a graph in terms of its degree sequence
- The maximum number of cycles in a graph with fixed number of edges
- Recent advances on the Hamiltonian problem: survey III
- Hamiltonian completions of sparse random graphs
- Increasing Hamiltonian paths in random edge orderings
- Random directed graphs are robustly Hamiltonian
- Finding Hamilton cycles in random graphs with few queries
- On the number of Hamiltonian cycles in Hamiltonian dense graphs
- Packing Hamilton cycles online
- An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
- Counting and packing Hamilton cycles in dense graphs and oriented graphs
- On the number of hamilton cycles in a random graph
- scientific article; zbMATH DE number 3922707 (Why is no real title available?)
- On a sparse random graph with minimum degree three: likely Pósa sets are large
- scientific article; zbMATH DE number 19173 (Why is no real title available?)
- Expected numbers at hitting times
- The threshold for hamilton cycles in the square of a random graph
- scientific article; zbMATH DE number 672355 (Why is no real title available?)
- Counting Hamilton cycles in sparse random directed graphs
- Sparse pseudo‐random graphs are Hamiltonian
- Optimal packings of Hamilton cycles in sparse random graphs
- Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs
- Edge correlations in Random regular hypergraphs and applications to subgraph testing
- Distributions of sparse spanning subgraphs in random graphs
- The threshold probability for long cycles
- Packing and counting arbitrary Hamilton cycles in random digraphs
- Packing, counting and covering Hamilton cycles in random directed graphs
- Packing, counting and covering Hamilton cycles in random directed graphs
- Color‐biased Hamilton cycles in random graphs
- Hamilton completion and the path cover number of sparse random graphs
- Towards the Erdős-Gallai cycle decomposition conjecture
- Powers of Hamilton cycles in pseudorandom graphs
- Cyclic subsets of tournaments
- On two Hamilton cycle problems in random graphs
This page was built for publication: On the Number of Hamilton Cycles in Sparse Random Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300478)
