Geodesics and almost geodesic cycles in random regular graphs
| dc.creator | Benjamini, Itai | |
| dc.creator | Hoppen, Carlos | |
| dc.creator | ofek, Eran | |
| dc.creator | Pralat, Pawel | |
| dc.creator | Wormald, Nick | |
| dc.date | 2006-10-02 | |
| dc.date.accessioned | 2026-07-07T07:28:37Z | |
| dc.date.available | 2026-07-07T07:28:37Z | |
| dc.description | 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 f(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 +f(n) and |C|=2\log_{d-1}n+O(f(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. | |
| dc.identifier | https://arxiv.org/abs/math/0610089 | |
| dc.identifier | http://arxiv.org/abs/math/0610089 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/117797 | |
| dc.subject | Metric Geometry | |
| dc.subject | Probability | |
| dc.title | Geodesics and almost geodesic cycles in random regular graphs | |
| dc.type | text |