Circulant graph

It is sometimes called a cyclic graph,[1] but this term has other meanings.

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.

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 rook can move between in a single move) is a circulant graph.

This is because its symmetries include as a subgroup the cyclic group Cmn

[2] 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.

[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.

Equivalently, a circulant numbering is a numbering of the vertices for which the adjacency matrix of the graph is a circulant matrix.

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.

[2] Toida's conjecture refines Ádám's conjecture by considering only a special class of circulant graphs, in which all of the differences between adjacent graph vertices are relatively prime to the number of vertices.

According to this refined conjecture, these special circulant graphs should have the property that all of their symmetries come from symmetries of the underlying additive group of numbers modulo n. It was proven by two groups in 2001 and 2002.

[5][6] There is a polynomial-time recognition algorithm for circulant graphs, and the isomorphism problem for circulant graphs can be solved in polynomial time.