Artículos de revistas
Geodesics and Almost Geodesic Cycles in Random Regular Graphs
Fecha
2011Registro en:
JOURNAL OF GRAPH THEORY, v.66, n.2, p.115-136, 2011
0364-9024
10.1002/jgt.20496
Autor
BENJAMINI, Itai
HOPPEN, Carlos
OFEK, Eran
PRATAT, Pawet
WORMALD, Nick
Institución
Resumen
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 omega(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+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(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. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011