TOPICS

# Circulant Graph

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 .

16-Cell, Andrásfai Graph, Antiprism Graph, Cocktail Party Graph, Complete Graph Complete Bipartite Graph, Cycle Graph, Empty Graph, Möbius Ladder, Octahedral Graph, Paley Graph, Pentatope Graph, Prism Graph, Square Graph, Tetrahedral Graph, Torus Grid Graph, Triangle Graph, Utility Graph

## Explore with Wolfram|Alpha

More things to try:

## References

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.

Circulant Graph

## Cite this as:

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