Uniform Generation of Unlabelled Graphs

Given the number of vertices \( n \), labelled graphs can easily be generated uniformly at random by simply selecting each edge independently with probability \( \frac{1}{2} \). With \( \frac{n(n-1)}{2} \) processors, this takes constant parallel time. In contrast, the problem of uniformly generating unlabelled graphs of size \( n \) is not so straightforward. In this paper, we describe an efficient parallelisation of a classic algorithm of Dixon and Wilf for the uniform generation of unlabelled graphs on \( n \) vertices. The algorithm runs in \( O(\log n) \) expected time on a CREW PRAM using \( n^2 \) processors.