On the number of Hamilton cycles in pseudo-random graphs

zbMATH Open1243.05141MaRDI QIDQ426784FDOQ426784

Authors Michael Krivelevich

Publication date 12 June 2012

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

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

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

zbMATH Keywords

\(d\)-regular graph

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

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

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)