
In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a circulant graph is an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
acted on by a
cyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
of
symmetries
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is invariant under some transformations ...
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
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
of the graph includes a
cyclic subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G.
Formally, given a group (mathematics), group under a binary operation  ...
that
acts transitively on the graph's vertices. In other words, the graph has an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphism ...
which is a
cyclic permutation
In mathematics, and in particular in group theory, a cyclic permutation is a permutation consisting of a single cycle. In some cases, cyclic permutations are referred to as cycles; if a cyclic permutation has ''k'' elements, it may be called a ''k ...
of its vertices.
*The graph has an
adjacency matrix
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
that is a
circulant matrix
In linear algebra, a circulant matrix is a square matrix in which all rows are composed of the same elements and each row is rotated one element to the right relative to the preceding row. It is a particular kind of Toeplitz matrix.
In numerica ...
.
*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
In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...
, and every rotational symmetry of the
polygon
In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain.
The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
is also a symmetry of the drawing.
*The graph is a
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...
of a
cyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
.
Examples
Every
cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
is a circulant graph, as is every
crown graph with number of vertices congruent to 2 modulo 4.
The
Paley graph
In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yiel ...
s of order (where is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
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
In number theory, an integer ''q'' is a quadratic residue modulo operation, modulo ''n'' if it is Congruence relation, congruent to a Square number, perfect square modulo ''n''; that is, if there exists an integer ''x'' such that
:x^2\equiv q \pm ...
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
In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the util ...
is a circulant graph, as is every
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
. A
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory ...
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
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
, then the
rook's graph (a graph that has a vertex for each square of an
chessboard
A chessboard is a game board used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During p ...
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 ''C
mn''
''C
m''×''C
n''. More generally, in this case, the
tensor product of graphs between any - and -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.
[Small Ramsey Numbers](_blank)
Stanisław P. Radziszowski, '' Electronic J. Combinatorics'', dynamic survey 1, updated 2014.
A specific example
The circulant graph
with jumps
is defined as the graph with
nodes labeled
where each node ''i'' is adjacent to 2''k'' nodes
.
* The graph
is
connected if and only if
.
* If
are fixed
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s then the number of
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
s
where
satisfies a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
of order
.
** In particular,
where
is the ''n''-th
Fibonacci number
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
.
Self-complementary circulants
A
self-complementary graph
In the mathematical field of graph theory, a self-complementary graph is a graph which is isomorphic to its complement. The simplest non-trivial self-complementary graphs are the path graph and the cycle graph. There is no known characteri ...
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
In mathematics, Paley graphs are undirected graphs constructed from the members of a suitable finite field by connecting pairs of elements that differ by a quadratic residue. The Paley graphs form an infinite family of conference graphs, which yiel ...
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
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
d 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
In mathematics, the term linear function refers to two distinct but related notions:
* In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For di ...
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
A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...
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.
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 . It was proven by two groups in 2001 and 2002.
Algorithmic questions
There is a
polynomial-time
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
recognition algorithm for circulant graphs, and the isomorphism problem for circulant graphs can be solved in polynomial time.
References
External links
*{{mathworld, title=Circulant Graph, urlname=CirculantGraph
Graph families
Regular graphs