 | ||
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.
Contents
Equivalent definitions
Circulant graphs can be described in several equivalent ways:
Examples
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
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.
A specific example
The circulant graph
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. 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. 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 n − 1 in such a way that, if some two vertices numbered x and y are adjacent, then every two vertices numbered z and (z − x + 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.
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.