# Circulant graph

For the square matrices, see Circulant matrix.
The Paley graph of order 13, an example of a circulant graph.

In graph theory, a circulant graph is an undirected graph that has a cyclic group of symmetries that includes a symmetry taking any vertex to any other vertex.

## Equivalent definitions

Circulant graphs can be described in several equivalent ways:[1]

• The automorphism group of the graph includes a cyclic subgroup that acts transitively on the graph's vertices.
• The graph has an adjacency matrix that is a circulant matrix.
• The n vertices of the graph can be numbered from 0 to n − 1 in such a way that, if some two vertices numbered x and (x +d) mod n are adjacent, then every two vertices numbered z and (z +d) mod n are adjacent.
• The graph can be drawn (possibly with crossings) so that its vertices lie on the corners of a regular polygon, and every rotational symmetry of the polygon is also a symmetry of the drawing.
• The graph is a Cayley graph of a cyclic group.[2]

## Examples

Every cycle graph is a circulant graph, as is every crown graph whose number of vertices is 2 (mod 4).

The Paley graphs of order n (where n is a prime number congruent to 1 modulo 4) is a graph in which the vertices are the numbers from 0 to n − 1 and two vertices are adjacent if their difference is a quadratic residue modulo n. Since the presence or absence of an edge depends only on the difference modulo n of two vertex numbers, any Paley graph is a circulant graph.

Every Möbius ladder is a circulant graph, as is every complete graph. A complete bipartite graph is a circulant graph if it has the same number of vertices on both sides of its bipartition.

If two numbers m and n are relatively prime, then the m × n rook's graph (a graph that has a vertex for each square of an m × n chessboard and an edge for each two squares that a chess rook can move between in a single move) is a circulant graph. This is because its symmetries include as a subgroup the cyclic group {{{1}}}. More generally, in this case, the tensor product of graphs between any m- and n-vertex circulants is itself a circulant.[1]

Many of the known lower bounds on Ramsey numbers come from examples of circulant graphs that have small maximum cliques and small maximum independent sets.[3]

## A specific example

The circulant graph $C_n^{s_1,\ldots,s_k}$ with jumps $s_1, \ldots, s_k$ is defined as the graph with $n$ nodes labeled $0, 1, \ldots, n-1$ where each node i is adjacent to 2k nodes $i \pm s_1, \ldots, i \pm s_k \mod n$.

• The graph $C_n^{s_1, \ldots, s_k}$ is connected if and only if $\gcd(n, s_1, \ldots, s_k) = 1$.
• If $1 \leq s_1 < \cdots < s_k$ are fixed integers then the number of spanning trees $t(C_n^{s_1,\ldots,s_k})=na_n^2$ where $a_n$ satisfies a recurrence relation of order $2^{s_k-1}$.
• In particular, $t(C_n^{1,2}) = nF_n^2$ where $F_n$ is the n-th Fibonacci number.

## Self-complementary circulants

A self-complementary graph is a graph in which replacing every edge by a non-edge and vice versa produces an isomorphic graph. For instance, a five-vertex cycle graph is self-complementary, and is also a circulant graph. More generally every Paley graph is a self-complementary circulant graph.[4] Horst Sachs showed that, if a number n has the property that every prime factor of n is congruent to 1 modulo 4, then there exists a self-complementary circulant with n vertices. He conjectured that this condition is also necessary: that no other values of n allow a self-complementary circulant to exist.[1][4] The conjecture was proven some 40 years later, by Vilfred.[1]

## Ádám's conjecture

Define a circulant numbering of a circulant graph to be a labeling of the vertices of the graph by the numbers from 0 to n − 1 in such a way that, if some two vertices numbered x and y are adjacent, then every two vertices numbered z and (zx + y) mod n are adjacent. Equivalently, a circulant numbering is a numbering of the vertices for which the adjacency matrix of the graph is a circulant matrix.

Let a be an integer that is relatively prime to n, and let b be any integer. Then the linear function that takes a number x to ax + b transforms a circulant numbering to another circulant numbering. András Ádám conjectured that these linear maps are the only ways of renumbering a circulant graph while preserving the circulant property: that is, if G and H are isomorphic circulant graphs, with different numberings, then there is a linear map that transforms the numbering for G into the numbering for H. However, Ádám's conjecture is now known to be false. A counterexample is given by graphs G and H with 16 vertices each; a vertex x in G is connected to the six neighbors x ± 1, x ± 2, and x ± 7 (modulo 16), while in H the six neighbors are x ± 2, x ± 3, and x ± 5 (modulo 16). These two graphs are isomorphic, but their isomorphism cannot be realized by a linear map.[1]

## References

1. Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J., Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36.
2. ^ Alspach, Brian (1997), "Isomorphism and Cayley graphs on abelian groups", Graph symmetry (Montreal, PQ, 1996), NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 497, Dordrecht: Kluwer Acad. Publ., pp. 1–22, MR 1468786.
3. ^ Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
4. ^ a b Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen 9: 270–288. MR 0151953..