Circulant graph

Circulant graphs can be described in several equivalent ways: • The automorphism group of the graph includes a cyclic subgroup that acts transitively on the graph's vertices. In other words, the graph has an automorphism which is a cyclic permutation of its vertices. • The graph has an adjacency matrix that is a circulant matrix. • The vertices of the graph can be numbered from 0 to in such a way that, if some two vertices numbered and are adjacent, then every two vertices numbered and 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. ==Examples==

Every cycle graph is a circulant graph, as is every crown graph with number of vertices congruent to 2 modulo 4. The Paley graphs of order (where is a prime number congruent to ) is a graph in which the vertices are the numbers from 0 to and two vertices are adjacent if their difference is a quadratic residue modulo . Since the presence or absence of an edge depends only on the difference modulo  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 and are relatively prime, then the rook's graph (a graph that has a vertex for each square of an 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 \simeq Cm×Cn. More generally, in this case, the tensor product of graphs between any - and -vertex circulants is itself a circulant. == 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 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 of prime order is a self-complementary circulant graph. Horst Sachs showed that, if a number has the property that every prime factor of is congruent to , then there exists a self-complementary circulant with vertices. He conjectured that this condition is also necessary: that no other values of allow a self-complementary circulant to exist. The conjecture was proven some 40 years later, by Vilfred. ==Á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 in such a way that, if some two vertices numbered and are adjacent, then every two vertices numbered and 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 be an integer that is relatively prime to , and let be any integer. Then the linear function that takes a number to 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 and are isomorphic circulant graphs, with different numberings, then there is a linear map that transforms the numbering for into the numbering for . However, Ádám's conjecture is now known to be false. A counterexample is given by graphs and with 16 vertices each; a vertex in is connected to the six neighbors , , and modulo 16, while in the six neighbors are , , and modulo 16. These two graphs are isomorphic, but their isomorphism cannot be realized by a linear map. ==Algorithmic questions==

There is a polynomial-time recognition algorithm for circulant graphs, and the isomorphism problem for circulant graphs can be solved in polynomial time. ==References==