Return a random regular graph of n nodes each with degree d, G_{n,d}. Return False if unsuccessful.
n*d must be even
Nodes are numbered 0...n-1. To get a uniform sample from the space of random graphs you should chose d<n^{1/3}.
For algorith see Kim and Vu’s paper.
Reference:
@inproceedings{kim-2003-generating,
author = {Jeong Han Kim and Van H. Vu},
title = {Generating random regular graphs},
booktitle = {Proceedings of the thirty-fifth ACM symposium on Theory of computing},
year = {2003},
isbn = {1-58113-674-9},
pages = {213--222},
location = {San Diego, CA, USA},
doi = {http://doi.acm.org/10.1145/780542.780576},
publisher = {ACM Press},
}
The algorithm is based on an earlier paper:
@misc{ steger-1999-generating,
author = "A. Steger and N. Wormald",
title = "Generating random regular graphs quickly",
text = "Probability and Computing 8 (1999), 377-396.",
year = "1999",
url = "citeseer.ist.psu.edu/steger99generating.html",
}