On the number of Hamilton cycles in pseudo-random graphs

zbMATH Open1243.05141arXiv1111.6261MaRDI QIDQ426784FDOQ426784

Authors: Michael Krivelevich 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We prove that if G is an (n,d,lambda)-graph (a d-regular graph on n vertices, all of whose non-trivial eigenvalues are at most lambda) and the following conditions are satisfied: 1. d/lambda >= (log n)^{1+epsilon} for some constant epsilon>0; 2.log d * lod (d/lambda) >> log n, then the number of Hamilton cycles in G is n!(d/n)^n(1+o(1))^n.

Full work available at URL: https://arxiv.org/abs/1111.6261

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Hamilton cycles in random subgraphs of pseudo-random graphs
• Pseudo-random graphs
• Powers of Hamilton cycles in pseudorandom graphs
• Sparse pseudo‐random graphs are Hamiltonian
• On the number of hamilton cycles in a random graph

zbMATH Keywords

\(d\)-regular graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45)

Cited In (17)

• Powers of Hamilton cycles in pseudorandom graphs
• Improved upper bounds on even-cycle creating Hamilton paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Recent advances on the Hamiltonian problem: survey III
• On the number of hamilton cycles in a random graph
• Hamilton cycles in random subgraphs of pseudo-random graphs
• Powers of Hamilton cycles in pseudorandom graphs
• Hamilton cycles in pseudorandom graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Packing, counting and covering Hamilton cycles in random directed graphs
• Pseudo-random graphs
• The number of Hamiltonian decompositions of regular graphs
• Sparse pseudo‐random graphs are Hamiltonian
• Generating and Counting Hamilton Cycles in Random Regular Graphs
• Edge correlations in Random regular hypergraphs and applications to subgraph testing

This page was built for publication: On the number of Hamilton cycles in pseudo-random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426784)