Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
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 
.
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.
Weisstein, Eric W. "Circulant Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CirculantGraph.html
Contact the MathWorld Team
circulant graph