Geodesics and almost geodesic cycles in random regular graphs |
| |
| Authors: | Itai Benjamini Carlos Hoppen Eran Ofek Pawe? Pra?at Nick Wormald |
| |
| Institution: | 1. Department of Mathematics The Weizmann Institute of Science Rehovot 76100, Israel;2. Instituto De MatemáTica E EstatíStica Universidade De S?o Paulo, S?O Paulo‐SP, Brazil;3. Department of Computer Science and Applied Mathematics The Weizmann Institute of Science, Rehovot 76100, Israel;4. Department of Mathematics, West Virginia University Morgantown, WV 26506‐6310;5. Department of Combinatorics and Optimization University of Waterloo, Waterloo, Ont., Canada N2L 3G1 |
| |
| Abstract: | 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 ω(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?1logd?1n+ ω(n) and |C| = 2logd?1n+ 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. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011 |
| |
| Keywords: | geodesics random regular graphs |
|
|
