Uniform generation of random regular graphs of moderate degree

Abstract

We show how to generate k-regular graphs on n vertices uniformly at random in expected time O(nk3), provided k = O(n 1 3). The algorithm employs a modification of a switching argument previously used to count such graphs asymptotically for k = o(n 1 3). The asymptotic formula is re-derived, using the new switching argument. The method is applied also to graphs with given degree sequences, provided certain conditions are met. In particular, it applies if the maximum degree is O(∥E(G)∥ 1 4). The method is also applied to bipartite graphs. Show more