TOPICS

Circulant Graph


CirculantGraphs

A circulant graph is a graph of n graph vertices in which the ith graph vertex is adjacent to the (i+j)th and (i-j)th graph vertices for each j in a list l. The circulant graph Ci_n(1,2,...,|_n/2_|) gives the complete graph K_n and the graph Ci_n(1) gives the cyclic graph C_n.

The circulant graph on n vertices on an offset list l 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 P_2, connected circulant graphs are biconnected, bridgeless, cyclic, Hamiltonian, LCF, regular, traceable, and vertex-transitive.

A graph G is a circulant iff the automorphism group of G contains at least one permutation consisting of a minimal cycle of length |V(G)|.

CirculantGraphEnumeration

The numbers of circulant graphs on n=1, 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 {1,2,...,|_n/2_|} since, for example, Ci_5(1)=Ci_5(2)=C_5. There is an easy formula for prime orders, and formulas are known for squarefree and prime-squared orders.

ConnectedCirculantGraphs

The numbers of connected circulant graphs on n=1, 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 K_(n×2), complete graphs, complete bipartite graphs K_(n,n), crown graphs 2n-1, empty graphs, rook graphs L_(k,n) for (k,n)=1, Möbius ladders, Paley graphs of prime order, prism graphs Y_n, and torus grid graphs C_m square C_n with (m,n)=1 (i.e., m and n relatively prime) corresponding to Ci_(mn)(m,n)) and where  square denotes a Cartesian product. Special cases are summarized in the table below.

Families of unit-distance connected circulant graphs include:

1. cycle graphs C_n=Ci_n(1),

2. Cartesian products of prism graphs C_n square P_2 and P_2, yielding torus grid graphs C_n square P_2 square P_2=C_4 square C_n=Ci_(n(n+1))(n,n+1).


See also

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

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 n and Degree 4 or 5" [Chinese]. Dianzi Keji Daxue Xuebao 25, 272-276, 1996.

Referenced on Wolfram|Alpha

Circulant Graph

Cite this as:

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

Subject classifications