𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonian cycles in random regular graphs

✍ Scribed by T.I Fenner; A.M Frieze

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
484 KB
Volume
37
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Uniqueness of maximal dominating cycles
Uniqueness of maximal dominating cycles in 3-regular graphs and of hamiltonian cycles in 4-regular graphs
✍ Herbert Fleischner πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 461 KB πŸ‘ 2 views

## Abstract We construct 3‐regular (cubic) graphs __G__ that have a dominating cycle __C__ such that no other cycle __C__~1~ of __G__ satisfies __V(C)__ βŠ† __V__(__C__~1~). By a similar construction we obtain loopless 4‐regular graphs having precisely one hamiltonian cycle. The basis for these const

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

Generating and Counting Hamilton Cycles
Generating and Counting Hamilton Cycles in Random Regular Graphs
✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 216 KB

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.