𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Deviation inequality for the number ofk-cycles in a random graph

✍ Scribed by Yanqing Wang; Fuqing Gao

Book ID
107531362
Publisher
Wuhan University
Year
2009
Tongue
English
Weight
247 KB
Volume
14
Category
Article
ISSN
1007-1202

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the number of hamilton cycles in a ra
On the number of hamilton cycles in a random graph
✍ C. Cooper; A. M. Frieze πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 576 KB

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n)('-')" distinct hamilton cycles for any fixed E > 0.

Limit distribution for the existence of
Limit distribution for the existence of hamiltonian cycles in a random graph
✍ JΓ‘nos KomlΓ³s; Endre SzemerΓ©di πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 874 KB

P&a proved that a random graph with clt log n edges is Hamiltonian with probability tending to 1 if c >3. Korsunov improved this by showing that, if Gn is a random graph with \*n log n + in log log n + f(n)n edges and f(n) --\*m, then G" is Hamiltonian, with probability tending to 1. We shall prove