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)
