A circulant graph is a graph of graph vertices in which the th graph vertex is adjacent to the th and th graph vertices for each in a list . The circulant graph gives the complete graph and the graph gives the cyclic graph .
The circulant graph on vertices on an offset list is implemented in the Wolfram Language as CirculantGraph[n, l]. Precomputed properties are available using GraphData["Circulant", n, l].
With the exception of the degenerate case of the path graph , connected circulant graphs are biconnected, bridgeless, cyclic, Hamiltonian, LCF, regular, traceable, and vertex-transitive.
A graph is a circulant iff the automorphism group of contains at least one permutation consisting of a minimal cycle of length .
The numbers of circulant graphs on , 2, ... nodes (counting empty graphs as circulant graphs) are 1, 2, 2, 4, 3, 8, 4, 12, ... (OEIS A049287), the first few of which are illustrated above. Note that these numbers cannot be counted simply by enumerating the number of nonempty subsets of since, for example, . There is an easy formula for prime orders, and formulas are known for squarefree and prime-squared orders.
The numbers of connected circulant graphs on , 2, ... nodes are 0, 1, 1, 2, 2, 5, 3, 8, ..., illustrated above.
Classes of graphs that are circulant graphs include the Andrásfai graphs, antiprism graphs, cocktail party graphs , complete graphs, complete bipartite graphs , crown graphs , empty graphs, rook graphs for , Möbius ladders, Paley graphs of prime order, prism graphs , and torus grid graphs with (i.e., and relatively prime) corresponding to ) and where denotes a Cartesian product. Special cases are summarized in the table below.
Families of unit-distance connected circulant graphs include:
1. cycle graphs ,
2. Cartesian products of prism graphs and , yielding torus grid graphs .