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, KC
graphs 
for 
(i.e., 
and 
relatively prime) and where 
denotes a Cartesian
product, rook graphs 
for 
, Möbius ladders,
Paley graphs of prime order, prism
graphs 
,
and torus grid graphs 
with 
corresponding to 
). 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 
.
The graph genus is known for all circulant graphs with genus 1 and 2 (Conder and Grande 2015, Metzger and Ulrigg 2025), though while
appears in the body
of Conder and Grande (2015), it was accidentally omitted from the enumeration of
genus 2 graphs in Theorem 3.
See also
16-Cell, Andrásfai Graph, Antiprism Graph, Cocktail Party Graph, Complete Graph Complete Bipartite Graph, Cycle Graph, Empty Graph, KC Graph, Möbius Ladder, Octahedral Graph, Paley Graph, Pentatope Graph, Prism Graph, Rook Graph, Square Graph, Tetrahedral Graph, Torus Grid Graph, Triangle Graph, Utility Graph
Explore with Wolfram|Alpha
References
Buckley, F. and Harary, F. Distance in Graphs. Redwood City, CA: Addison-Wesley, 1990.Conder , M.
and Grande, R. "On Embeddings of Circulant Graphs." Elec. J. Combin. 22,
No. 2, Article P2.28, 2015. https://doi.org/10.37236/4013.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.Metzger, A. and Ulrigg, A. "An Efficient Genus
Algorithm Based on Graph Rotations." 29 Jun 2025. https://arxiv.org/abs/2411.07347.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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Circulant Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CirculantGraph.html