Circulant graph

In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings. 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 a graph automorphism, which is a cyclic permutation of its 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. Every cycle graph is a circulant graph, as is every crown graph with 2 modulo 4 vertices. 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 Cmn Cm×Cn. More generally, in this case, the tensor product of graphs between any m- and n-vertex circulants is itself a circulant.