Random regular graph

A random r-regular graph is a graph selected from \mathcal{G}_{n,r} , which denotes the probability space of all r-regular graphs on n vertices, where 3 \le r and nr is even. 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.

A random r-regular graph is a graph selected from \mathcal{G}_{n,r} , which denotes the probability space of all r-regular graphs on n vertices, where 3 \le r and nr is even. 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 m –regular graphs hold asymptotically almost surely. In particular, for r \ge 3 , a random r-regular graph of large size is asymptotically almost surely r-connected. In other words, although r –regular graphs with connectivity less than r exist, the probability of selecting such a graph tends to 0 as n increases. If \epsilon > 0 is a positive constant, and d is the least integer satisfying (r-1)^{d-1} \ge (2 + \epsilon)rn \ln n 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. The distribution of the number of short cycles is also known: for fixed m \ge 3 , let Y_3,Y_4,...Y_m be the number of cycles of lengths up to m . Then the Y_i are asymptotically independent Poisson random variables with means \lambda_i=\frac{(r-1)^i}{2i} ==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. A refinement of this method was developed by Brendan McKay and Nicholas Wormald. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1289218115 under CC BY-SA 4.0; modifications have been made.