On Sat, Dec 24, 2011 at 9:43 AM, Oliver Kullmann
<O.Kullmann at swansea.ac.uk> wrote:
> Hello,
>
> after load(graphs),
>
> calling
>
> random_regular_graph(1);
> random_regular_graph(2);
>
> enters apparently an infinite loop, which should at least
> be documented.
For a cubic graph you need at least 4 vertices. The function should
signal an error if you request less.
> And random_regular_graph(n) for n >= 3 creates a graph
> with n+1 vertices, not with n vertices, as specified:
>
> (%i6) random_regular_graph(3);
> Evaluation took 0.0390 seconds (0.0390 elapsed)
> (%o6) ?GRAPH\(4\ vertices\,\ 6\ edges\)
For a cubic graph you need an even number of vertices. If you request
an odd number of vertices, the number is silently increased by one.
> Finally, it would also be nice if a specification for the method
> of creating a random_regular_graph would be given (or if it is
> the uniform distribution over all regular graphs for the given parameters,
> then this should be stated).
For a d-regular graph on n vertices, n*d vertices are initially
created (d copies for each vertex) and a random matching on these
vertices is computed. The d copies of each vertex are then identified
to obtain a d-regular graph.
HTH, Andrej