Hamiltonian cycles in Dirac graphs |
| |
Authors: | Bill Cuckler Jeff Kahn |
| |
Institution: | (1) Department of Mathematical Sciences, University of Delaware, 501 Ewing Hall, Newark, DE 19716-2553, USA;(2) Department of Mathematics, Rutgers University, Hill Center, 110 Frelinghuysen Road, Piscataway, NJ 08854-8019, USA |
| |
Abstract: | We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=( V,E), the number, Ψ( G), of Hamiltonian cycles in G is at least $exp_2 2h(G) - n\log e - o(n)],$ where h( G)=maxΣ e x e log(1/ x e ), the maximum over x: E → ? + satisfying Σ e?υ x e = 1 for each υ ∈ V, and log =log 2. (A second paper will show that this bound is tight up to the o( n).) We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) n . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) n , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work. |
| |
Keywords: | Mathematics Subject Classification (2000)" target="_blank">Mathematics Subject Classification (2000) 05A16 05C38 05C45 05D40 05C70 |
本文献已被 SpringerLink 等数据库收录! |
|