Circulant graph

Circulant graph
The Paley graph of order 13, an example of a circulant graph.
Crown graphs with six, eight, and ten vertices.

In graph theory, a circulant graph is an undirected graph that has a cyclic group of symmetries that includes a symmetry taking any vertex to any other vertex.

Contents

Equivalent definitions

Circulant graphs can be described in several equivalent ways:[1]

  • The automorphism group of the graph includes a cyclic subgroup that acts transitively on the graph's 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 y are adjacent, then every two vertices numbered z and zx + y (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. (However, reflecting the polygon may give a different drawing.)
  • The circulant graph  C_n^{s_1,\ldots,s_k} with jumps  s_1, \ldots, s_k is often defined as the graph with n nodes labeled  \{0, \ldots, n-1\} each node i being adjacent to the nodes  i \pm s_1, \ldots i \pm s_k \mod n .

Examples

Every cycle graph is a circulant graph, as is every crown graph.

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 . More generally, in this case, the tensor product of graphs between any m- and n-vertex circulants is itself a circulant.[1]

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.[2]

Properties

From the last definiton it follows that  C_n^{s_1, \ldots, s_k} is a 2k regular graph.  C_n^{s_1, \ldots, s_k} is connected if and only if  \gcd(n, s_1, \ldots, s_k) > 1 . It is known that if  1 \leq s_1 < \cdots < s_k are fixed integers then the number of spanning trees  t(C_n^{s_1,\ldots,s_k}) is  na_n^2 where an satisfies a recurrence relation of order 2^{s_k-1} . This fact can be used to derived the well known identity  t(C_n^{1,2}) = nf_n^2 where fn denotes 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 is a self-complementary circulant graph.[3] Horst Sachs showed that, if a number n has the property that every prime factor of n must be 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.[1][3] The conjecture was proven some 40 years later, by Vilfred.[1]

Ádam'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 zx + 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. Ádam 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, Ádam'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, while in H the six neighbors are x ± 2, x ± 3, and x ± 5. These two graphs are isomorphic, but their isomorphism cannot be realized by a linear map.[1]

References

  1. ^ a b c d e Vilfred, V. (2004), "On circulant graphs", in Balakrishnan, R.; Sethuraman, G.; Wilson, Robin J., Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001), Alpha Science, pp. 34–36, http://books.google.com/books?id=wG-08Lv8E-0C&pg=PA34 .
  2. ^ Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
  3. ^ a b Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen 9: 270–288. MR0151953. .

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Circulant matrix — In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are… …   Wikipedia

  • Rook's graph — infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… …   Wikipedia

  • Regular graph — In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a kregular graph or regular graph of degree… …   Wikipedia

  • Paley graph — infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs …   Wikipedia

  • Vertex-transitive graph — In mathematics, a vertex transitive graph is a graph G such that, given any two vertices v1 and v2 of G , there is some automorphism : f : V(G) → V(G) such that : f (v1) = v2. In other words, a graph is vertex transitive if its automorphism group …   Wikipedia

  • Cycle graph (disambiguation) — A cycle graph or cyclic graph is a connected, 2 regular graph.Cycle graph or cyclic graph may also refer to: * Cycle graph (algebra), a diagram representing the cycles determined by taking powers of group elements * Circulant graph * A graph… …   Wikipedia

  • Crown graph — Crown graphs with six, eight, and ten vertices. In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j. The crown… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Cyclic (mathematics) — There are many terms in mathematics that begin with cyclic: Cyclic chain rule, for derivatives, used in thermodynamics Cyclic code, linear codes closed under cyclic permutations Cyclic convolution, a method of combining periodic functions Cycle… …   Wikipedia

  • Möbius ladder — Two views of the Möbius ladder M16. In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n cycle by adding edges (called rungs ) connecting opposite pairs of vertices in the cycle. It… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”