Circulant graph

In graph theory, a circulant graph is an undirected graph that has a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term also is given other meanings.

Circulant graphs can be described in several equivalent ways:

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 \times n$ rook's graph (a graph that has a vertex for each square of an $m \times 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 C_mn $\simeq$ C_m×C_n. More generally, in this case, the tensor product of graphs between any $m$ - and $n$ -vertex circulants is itself a circulant.

...
Wikipedia