Cycle graph
|
|
Directed_cycle.png
In graph theory, a cycle graph or circle 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 <math>n<math> vertices is called <math>C_n<math>.
A directed cycle graph or a dicycle graph is a diconnected cycle graph, that is all directed edges in the cycle point in the same direction.
A cycle with an even number of vertices is called even cycle, a cycle with an odd number of vertices is called odd cycle.
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.
Properties
A circle graph is:
- connected
- 2-regular
- Eulerian
- Hamiltonian
- symmetric
- 2-vertex colorable and 2-edge colorable if it has an even number vertices
- 3-vertex colorable and 3-edge colorable if it has an odd number of vertices.
In addition:
- Any connected graph with a subgraph that is a cycle is not a tree.
- Cycles with an even number of vertices are bipartite, cycles with an odd number are not.
- Cycles with an even number of vertices can be decomposed into a minimum of 2 independent sets (that is, <math>\alpha(n)=2<math>), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, <math>\alpha(n)=3<math>).
There is a directed cycle through any two vertices in a strongly connected component.
See also
- Cycle graph (group) — using cycle graphs to illustrate the structure of small finite groups
References
- Eric W. Weisstein, Cycle Graph (http://mathworld.wolfram.com/CycleGraph.html) at MathWorld.