A '''random ''r''-regular graph''' is a graph selected from <math>\mathcal{G}_{n,r}</math>, which denotes the probability space of all ''r''-regular graphs on <math>n</math> vertices, where <math>3 \le r < n</math> and <math>nr</math> is even.<ref>Béla Bollobás, ''Random Graphs'', 2nd edition, Cambridge University Press (2001), section 2.4: Random Regular Graphs</ref> It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.
==Properties of random regular graphs== As with more general random graphs, it is possible to prove that certain properties of random <math>m</math>–regular graphs hold asymptotically almost surely. In particular, for <math> r \ge 3 </math>, a random ''r''-regular graph of large size is asymptotically almost surely ''r''-connected.<ref>Bollobás, section 7.6: Random Regular Graphs</ref> In other words, although <math>r</math>–regular graphs with connectivity less than <math>r</math> exist, the probability of selecting such a graph tends to 0 as <math>n</math> increases.
If <math>\epsilon > 0</math> is a positive constant, and <math>d</math> is the least integer satisfying
<math>(r-1)^{d-1} \ge (2 + \epsilon)rn \ln n</math>
then, asymptotically almost surely, a random ''r''-regular graph has diameter at most ''d''. There is also a (more complex) lower bound on the diameter of ''r''-regular graphs, so that almost all ''r''-regular graphs (of the same size) have almost the same diameter.<ref>Bollobás, section 10.3: The Diameter of Random Regular Graphs</ref>
The distribution of the number of short cycles is also known: for fixed <math>m \ge 3</math>, let <math>Y_3,Y_4,...Y_m</math> be the number of cycles of lengths up to <math>m</math>. Then the <math>Y_i</math>are asymptotically independent Poisson random variables with means<ref>Bollobás, section 2.4: Random Regular Graphs (Corollary 2.19)</ref>
<math>\lambda_i=\frac{(r-1)^i}{2i}</math>
==Algorithms for random regular graphs== It is non-trivial to implement the random selection of ''r''-regular graphs efficiently and in an unbiased way, since most graphs are not regular. The ''pairing model'' (also ''configuration model'') is a method which takes ''nr'' points, and partitions them into ''n'' buckets with ''r'' points in each of them. Taking a random matching of the ''nr'' points, and then contracting the ''r'' points in each bucket into a single vertex, yields an ''r''-regular graph or multigraph. If this object has no multiple edges or loops (i.e. it is a graph), then it is the required result. If not, a restart is required.<ref>N. Wormald, "Models of Random Regular Graphs," in ''Surveys in Combinatorics'', Cambridge University Press (1999), pp 239-298</ref>
A refinement of this method was developed by Brendan McKay and Nicholas Wormald.<ref>B. McKay and N. Wormald, "Uniform Generation of Random Regular Graphs of Moderate Degree," ''Journal of Algorithms'', Vol. 11 (1990), pp 52-67: [http://cs.anu.edu.au/~bdm/papers/RandRegGen.pdf]</ref>
==References== {{reflist}}
Category:Random graphs Category:Regular graphs