| Full text | |
| Author(s): |
Total Authors: 5
|
| Affiliation: | [1] Weizmann Inst Sci, Dept Math, IL-76100 Rehovot - Israel
[2] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
[3] Weizmann Inst Sci, Dept Comp Sci & Appl Math, IL-76100 Rehovot - Israel
[4] W Virginia Univ, Dept Math, Morgantown, WV 26506 - USA
[5] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1 - Canada
Total Affiliations: 5
|
| Document type: | Journal article |
| Source: | JOURNAL OF GRAPH THEORY; v. 66, n. 2, p. 115-136, FEB 2011. |
| Web of Science Citations: | 4 |
| 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 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 (AU) | |