Diameters of random circulant graphs |
| |
Authors: | Jens Marklof Andreas Strömbergsson |
| |
Institution: | 1. School of Mathematics, University of Bristol, Bristol, BS8 1TW, UK 2. Department of Mathematics, Uppsala University, Box 480, SE-75106, Uppsala, Sweden
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|