Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a hard time to find a way to construct a k-regular graph out of n vertices. There seems to be a lot of theoretical material on regular graphs on the internet but I can't seem to extract construction rules for regular graphs.

My preconditions are

k<n and (n%2 == 0 or k%2 == 0)

Is an adjacency matrix the way to go here? If so, how would I use it?

Is this even a mathematical problem?

share|improve this question

2 Answers 2

up vote 11 down vote accepted

If $k=2m$ is even, put all the vertices around a circle, and join each to its $m$ nearest neighbors on either side.

If $k=2m+1$ is odd, and $n$ is even, put the vertices on a circle, join each to its $m$ nearest neighbors on each side, and also to the vertex directly opposite.

share|improve this answer
2  
Note that for $k \gt 1$ the resulting $k$-regular graph is connected, because it contains the $n$-cycle solution given by $k=2$. –  hardmath May 21 '12 at 3:29

Once you have an initial $k$-regular graph, you can generate many more by randomly applying the following simple switching operation:

Switching operation illustration

provided it does not introduce a parallel edge or loop.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.