Geodesics and almost geodesic cycles in random regular graphs
  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. 
Itai Benjamini, Carlos Hoppen, Eran ofek, Pawel Pralat, Nick Wormald