𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating and Counting Hamilton Cycles in Random Regular Graphs

✍ Scribed by Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
216 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ε½ . with vertex set n . We describe polynomial time algorithms that whp i find a Ε½ . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

πŸ“œ SIMILAR VOLUMES

Hamilton cycles in regular graphs
Hamilton cycles in regular graphs
✍ Bill Jackson πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 135 KB

## UNIVERSIW OF WATERLOO ' The research reported here has been sponsored by the Canadian Commonwealth Association.

Random Matchings Which Induce Hamilton C
Random Matchings Which Induce Hamilton Cycles and Hamiltonian Decompositions of Random Regular Graphs
✍ Jeong Han Kim; Nicholas C. Wormald πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 215 KB

Select four perfect matchings of 2n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set

Geodesics and almost geodesic cycles in
Geodesics and almost geodesic cycles in random regular graphs
✍ Itai Benjamini; Carlos Hoppen; Eran Ofek; PaweΕ‚ PraΕ‚at; Nick Wormald πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 198 KB

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d G (u, v) is at least d C (u, v)-e(n). Let (n) be any function tending to infin