Английская Википедия:Circulant graph

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Paley13.svg

The Paley graph of order 13, an example of a 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.

Equivalent definitions

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 Шаблон:Mvar vertices of the graph can be numbered from 0 to Шаблон:Math in such a way that, if some two vertices numbered Шаблон:Mvar and Шаблон:Math are adjacent, then every two vertices numbered Шаблон:Mvar and Шаблон:Math 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 Шаблон:Nowrap vertices.

The Paley graphs of order Шаблон:Mvar (where Шаблон:Mvar is a prime number congruent to Шаблон:Nowrap) is a graph in which the vertices are the numbers from 0 to Шаблон:Math and two vertices are adjacent if their difference is a quadratic residue modulo Шаблон:Mvar. Since the presence or absence of an edge depends only on the difference modulo Шаблон:Mvar 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 Шаблон:Mvar and Шаблон:Mvar are relatively prime, then the Шаблон:Math rook's graph (a graph that has a vertex for each square of an Шаблон:Math 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 <math>\simeq</math> C_m×C_n. More generally, in this case, the tensor product of graphs between any Шаблон:Mvar- and Шаблон:Mvar-vertex circulants is itself a circulant.

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 <math> C_n^{s_1,\ldots,s_k} </math> with jumps <math> s_1, \ldots, s_k </math> is defined as the graph with <math> n </math> nodes labeled <math>0, 1, \ldots, n-1</math> where each node i is adjacent to 2k nodes <math>i \pm s_1, \ldots, i \pm s_k \mod n</math>.

• The graph <math>C_n^{s_1, \ldots, s_k}</math> is connected if and only if <math>\gcd(n, s_1, \ldots, s_k) = 1</math>.
• If <math> 1 \leq s_1 < \cdots < s_k </math> are fixed integers then the number of spanning trees <math>t(C_n^{s_1,\ldots,s_k})=na_n^2</math> where <math>a_n</math> satisfies a recurrence relation of order <math>2^{s_k-1}</math>.
  • In particular, <math>t(C_n^{1,2}) = nF_n^2 </math> where <math>F_n</math> 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 Шаблон:Mvar has the property that every prime factor of Шаблон:Mvar is congruent to Шаблон:Nowrap, then there exists a self-complementary circulant with Шаблон:Mvar vertices. He conjectured that this condition is also necessary: that no other values of Шаблон:Mvar 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 Шаблон:Math in such a way that, if some two vertices numbered Шаблон:Mvar and Шаблон:Mvar are adjacent, then every two vertices numbered Шаблон:Mvar and Шаблон:Math 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 Шаблон:Mvar be an integer that is relatively prime to Шаблон:Mvar, and let Шаблон:Mvar be any integer. Then the linear function that takes a number Шаблон:Mvar to Шаблон:Math 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 Шаблон:Mvar and Шаблон:Mvar are isomorphic circulant graphs, with different numberings, then there is a linear map that transforms the numbering for Шаблон:Mvar into the numbering for Шаблон:Mvar. However, Ádám's conjecture is now known to be false. A counterexample is given by graphs Шаблон:Mvar and Шаблон:Mvar with 16 vertices each; a vertex Шаблон:Mvar in Шаблон:Mvar is connected to the six neighbors Шаблон:Math, Шаблон:Math, and Шаблон:Math modulo 16, while in Шаблон:Mvar the six neighbors are Шаблон:Math, Шаблон:Math, and Шаблон:Math modulo 16. These two graphs are isomorphic, but their isomorphism cannot be realized by a linear map.

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 Шаблон:Math. It was proven by two groups in 2001 and 2002.

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.

External links

• Шаблон:Mathworld