Cycle graph

This article is about connected, 2-regular graphs. For other uses, see Cyclic graph.
Cycle graph

A cycle graph of length 6
Vertices n
Edges n
Girth n
Automorphisms 2n (Dn)
Chromatic number 3 if n is odd
2 if n is even
Chromatic index 3 if n is odd
2 if n is even
Spectrum {2 cos(2 k π / n); k=1, ... ,n}[1]
Properties 2-regular
Unit distance

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 connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.


There are many synonyms for "cycle graph". These include simple cycle graph and cyclic graph, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, cycle, polygon, or n-gon are also often used. A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle.


A cycle graph is:

In addition:

Directed cycle graph

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction.

In a directed graph, a set of edges which contains at least one edge (or arc) from each directed cycle is called a feedback arc set. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set.

A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.

Directed cycle graphs are Cayley graphs for cyclic groups (see e.g. Trevisan).

See also

Wikimedia Commons has media related to Cycle graphs.


(discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams)

This article is issued from Wikipedia - version of the 11/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.