Models of Random Regular Graphs

Abstract

This is a survey of results on properties of random regular graphs, together with an exposition of some of the main methods of obtaining these results. Related results on asymptotic enumeration are also presented, as well as various generalisations to random graphs with given degree sequence. A major feature in this area is the small subgraph conditioning method. When applicable, this establishes a relationship between random regular graphs with uniform distribution, and non-uniform models of random regular graphs in which the probability of a graph G is weighted according to the number of subgraphs that G has of a certain type. Information can be obtained in this way on the probability of existence of various types of spanning subgraphs, such as Hamilton cycles and decompositions into perfect matchings. Uniformly distributed labelled random regular graphs receive most of the attention, but also included are several non-uniform models which come about in a natural way. Some of these appear as spin-offs from the small subgraph conditioning method, and some arise from algorithms which use simple approaches to generating random regular graphs. A quite separate role played by algorithms is in the derivation of random graph properties by analysing the performance of an appropriate greedy algorithm on a random regular graph. Many open problems and conjeetures are given.