Geodesics and almost geodesic cycles in random regular graphs

Details Geodesics and almost geodesic cycles in random regular graphs Geodesics and almost geodesic cycles in random regular graphs

2006-10-02

arxiv.org/abs/math/0610089v1

Mathematics

Metric Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Geodesics and almost geodesic cycles in random regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Geodesics and almost geodesic cycles in random regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geodesics and almost geodesic cycles in random regular graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-589203