Diameters of random circulant graphs

Details Diameters of random circulant graphs Diameters of random circulant graphs

2011-03-16

arxiv.org/abs/1103.3152v2

Mathematics

Combinatorics

A few typos removed; arxiv identifier added for reference [38]

Scientific paper

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n^{1/k}, and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.

Affiliated with

Also associated with

No associations

Rating

Diameters of random circulant 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 Diameters of random circulant graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diameters of random circulant graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263030