𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Geodesics and almost geodesic cycles in random regular graphs

✍ Scribed by Itai Benjamini; Carlos Hoppen; Eran Ofek; Paweł Prałat; Nick Wormald

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
198 KB
Volume
66
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log d-1 log d-1 n+ (n) and |C| = 2 log d-1 n+O( (n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph.

📜 SIMILAR VOLUMES

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.

The asymptotic distribution of long cycl
The asymptotic distribution of long cycles in random regular graphs
✍ Hans Garmo 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 580 KB

The asymptotic distribution of the number of cycles of length l in a random r-regular graph is determined. The length of the cycles is defined as a function of the Ž . Ž . number of vertices n, thus l s l n , and the length satisfies l n ª ϱ as n ª ϱ. The limiting Ž . Ž . distribution turns out to

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