Circulant graphs

A set of graphs that have some symmetric properties are the circulant graphs, which are defined by an integer \(n\) and a subset, \(C\), of the integers \(1, 2, ..., n-1\).
These are graphs over \(n\) vertices, which we take to be numbered from \(1\) to \(n\), where two vertices i and j are connected provided \(j-i\in{C}\), under arithmetic modulo \(n\) (or equivalently, since the graph is undirected, if \(i-j\in{C}\)).

See Godsil and Royle for further info.

We can construct a circulant graph in R using the following function:

make_circulant_graph <- function(n, C){
    # R function to construct a circulant graph using 'igraph'
    # See Godsil and Royle for the definition of a circulant graph
    # Note that the function uses igraph naming convention make_xyz<_graph>()
    # n is the number of vertices (here numbered from 1 to n)
    # C is a set of values
    # - Let i and j be numbered vertices (min=1, max=n)
    # - Then i and j are linked by an undirected edge if (j-i mod n) is in C
    require('igraph')
    if(n==0){
        return(make_ring(n = 0))
        }
    stopifnot(n>0)
    stopifnot(all(C %in% 1:(n-1)))
    edgelist <- lapply(1:n, function(i){
        modulo <- ((1:n) - i) %% n
        neighbours <- which(modulo %in% C)
        as.vector(t(cbind(i, neighbours)))
        })
    g <- simplify(
        make_graph(unlist(edgelist), n = n, directed = FALSE)
        )
    return(g)
    }

A cycle graph is a circulant graph so we should be able to construct the cycle-graph on 4 vertices that was made in an earlier post using igraph::make_ring using the following code:

g1 <- make_circulant_graph(n = 4, C = 1)
plot(g1)

Also, we can make graphs that are a bit more interesting:

g2 <- make_circulant_graph(n = 10, C = c(1, 3, 4))

plot(g2)

The plotted graph doesn't illuminate the symmetry of the graph, though. So we place the vertices in order around an invisible circle:

trigseq <- (2/10)*pi*(1:10)

g2$layout <- cbind(sin(trigseq), cos(trigseq))

plot(g2)