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 a list of nodes is implemented as CirculantGraph[n, l] in the Mathematica package Combinatorica`) , and 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, LCFLCF Notation, 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, ... (Sloane's 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, lattice graphs for , Möbius ladder graphs, Paley graphs of prime order, prism graphs , and torus grid graphs . Special cases are summarized in the table below.

graph	symbol
2-path graph
triangle graph
square graph
tetrahedral graph
5-cycle graph
pentatope graph
6-cycle graph
octahedral graph
utility graph
3-prism graph
6-complete graph
7-cycle graph
7-complete graph
8-cycle graph
4-antiprism graph
(4,4)-complete bipartite graph
4-Möbius ladder graph
16-cell graph
8-complete graph
9-cycle graph
9-complete graph
10-cycle graph
5-antiprism graph
5-crown graph
5-Möbius ladder graph
5-prism graph
(5,5)-complete bipartite graph
5-cocktail party graph
(5,5)-torus grid graph
10-complete graph

The circulant graph is the Cayley graph of the permutations 1, 2, 3, 5, 4, 1, 2, 4, 3, 5, 2, 1, 3, 5, 4, 2, 1, 5, 4, 3.

Buckley, F. and Harary, F. Distance in Graphs. Redwood City, CA: Addison-Wesley, 1990.

Golin, M. J. and Leung, Y. C. "Unhooking Circulant Graphs: a Combinatorial Method for Counting Spanning Trees and Other Parameters." In Graph-Theoretic Concepts in Computer Science. Revised Papers from the 30th International Workshop (WG 2004) Held in Bad Honnef, June 21-23, 2004 (Ed. J. Hromkovič, M. Nagl, and B. Westfechtel). Berlin, Germany: Springer-Verlag, pp. 296-307, 2004.

Lecture Notes in Comput. Sci., 3353, Springer, Berlin, 2004. Liskovets, V. A.; and Pöschel, R. "On the Enumeration of Circulant Graphs of Prime-Power and Square-Free Orders." Preprint. MATH-AL-8-1996, TU-Dresden.

Klin, M.; Liskovets, V.; and Pöschel, R. "Analytical Enumeration of Circulant Graphs with Prime-Squared Number of Vertices." Sém. Lothar. Combin. 36, Art. B36d, 1996.

Muzychuk, M. "A Solution of the Isomorphism Problem for Circulant Graphs." Proc. London Math. Soc. 88, 1-41, 2004.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 99 and 140, 1990.

Zhou, A. and Zhang, X. D. "Enumeration of Circulant Graphs with Order and Degree 4 or 5" [Chinese]. Dianzi Keji Daxue Xuebao 25, 272-276, 1996.

CITE THIS AS:

Weisstein, Eric W. "Circulant Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CirculantGraph.html