Uniform generation of random regular graphs of moderate degree

Brendan D. McKay, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

97 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)52-67
Number of pages16
JournalJournal of Algorithms
Volume11
Issue number1
DOIs
Publication statusPublished - 1990
Externally publishedYes

Cite this