CYCLE GRAPH

In graph theory, a 'cycle 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 ''C_n''. The number of vertices in a ''C_n'' equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.

Contents

A note on terminology

Properties

Directed cycle graph

External links

A note on terminology

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'.

Properties

A cycle graph is:

★ connected

★ 2-regular

★ Eulerian

★ Hamiltonian

★ 2-vertex colorable, if and only if it has an even number of vertices

★ 2-edge colorable, if and only if it has an even number of vertices

★ 3-vertex colorable and 3-edge colorable, if it has an odd number of vertices

★ A unit distance graph
In addition:

★ Cycles with an even number of vertices are bipartite; cycles with an odd number are not. More generally, a graph is bipartite if and only if it has no odd cycles (Kőnig, 1936).

★ Cycles with an even number of vertices can be decomposed into a minimum of 2 independent sets (that is, ), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, ).

★ As cycle graphs can be drawn as regular polygons, the symmetries of an ''n''-cycle are the same as those of a regular polygon with ''n'' sides, the dihedral group of order 2''n''. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the ''n''-cycle is a symmetric graph.

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).

External links

★ Eric W. Weisstein, Cycle Graph at MathWorld. (MathWorld discusses both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams in the same article.)

★ Luca Trevisan, Characters and Expansion.