2006/10/02 by Itaï Benjamini, Itai Benjamini, Carlos Hoppen +10
Mathematics · #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Metric Geometry (math.MG) #Probability (math.PR) #math.MG #math.PR
paper · pdf · doi:10.48550/arxiv.math/0610089
arxiv created 2006/10/02 · openalex publication_date 2006/10/02 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 dG(u,v) is at least dC(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)= logd-1 logd-1 n +f(n) and |C|=2logd-1n+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.