14
$\begingroup$

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

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

Is this even a mathematical problem?

3 Answers 3

21

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.

  • 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$.2012-05-21
6

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.

2

I just finished this question from Allen Downey's book Think Complexity, and thought I'll just share my algorithm (which is the same as Gerry's answer but just fleshed out) :

Preconditions: 0 < k and k < n

**If n is odd, k must be even

Number of Vertex (n) : Possible Number of degrees for each Vertex (k)                   2  :  1                   3  :  2                   4  :  1,2,3                   5  :  2,4                   6  :  1,2,3,4,5                   7  :  2,4,6                   8  :  1,2,3,4,5,6,7                   9  :  2,4,6,8                  10  :  1,2,3,4,5,6,7,8,9 

Examples:

if n is 7:     if k is 2:         make_edge_for_each_vertice_x_steps_away(1)     if k is 4:         make_edge_for_each_vertice_x_steps_away(1)         make_edge_for_each_vertice_x_steps_away(3)     if k is 6:         make_edge_for_each_vertice_x_steps_away(1)         make_edge_for_each_vertice_x_steps_away(3)         make_edge_for_each_vertice_x_steps_away(5)  if n is 8:     if k is 1:         make_edge_for_each_vertice_x_steps_away(4)     if k is 2:         make_edge_for_each_vertice_x_steps_away(1)     if k is 3:         make_edge_for_each_vertice_x_steps_away(4)         make_edge_for_each_vertice_x_steps_away(3)     if k is 4:         make_edge_for_each_vertice_x_steps_away(1)         make_edge_for_each_vertice_x_steps_away(2)     if k is 5:         make_edge_for_each_vertice_x_steps_away(4)         make_edge_for_each_vertice_x_steps_away(3)         make_edge_for_each_vertice_x_steps_away(2)     if k is 6:         make_edge_for_each_vertice_x_steps_away(1)         make_edge_for_each_vertice_x_steps_away(2)         make_edge_for_each_vertice_x_steps_away(3)     if k is 7:         make_edge_for_each_vertice_x_steps_away(4)         make_edge_for_each_vertice_x_steps_away(3)         make_edge_for_each_vertice_x_steps_away(2)         make_edge_for_each_vertice_x_steps_away(1)  make_edge_for_each_vertice_x_steps_away(x):     for each vertice, adds an edge to a neighbor x steps away.      if x == 1, edges will be created between v1 and v2, v2 and v3,..., vn to v1 

There is a pattern where

-If n is odd, we add edges between vertices x positions away, where x is all odd numbers between 1 to k.

-If n is even, and k is even, we add edges between vertices x positions away, where x is a range of numbers starting from 1 to n/2, and the range of these numbers is limited by the number of even numbers from 1 to k, including k

-If n is even, and k is odd, we add edges between vertices x positions away, where x is a range of numbers starting from n/2 to 1, and the range of these numbers is limited by the number of odd numbers from 1 to k, including k

Algorithm:

Layout_all_vertices_in_a_circle() if n is even:     if k is even:         countEvenNumbers = n/2         #add an edge for each even number between 1 to k, including k         for i in range(countEvenNumbers):             make_edge_for_each_vertice_x_steps_away(i+1)     else if k is odd:         countOddNumbers = ((n-1)/2) + 1         #add an edge for each odd number between 1 to k, including 1 and k         for i in range(countOddNumbers):             make_edge_for_each_vertice_x_steps_away((n/2)-i)  if n is odd:     for i in range(1, k):         if i is odd:             make_edge_for_each_vertice_x_steps_away(i) 

Hope this helps!