Cycle graph
Encyclopedia : C : CY : CYC : 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 two, that is, every vertex has exactly two edges incident with it.
A note on terminology
There are many synonyms for "cycle-graph." These include simple cycle graph and cyclic graph, although the latter term appears to be used more often by non-graph theorists. Among graph theorists, cycle, polygon, or n-gon are also often used. More specifically, a cycle with an even number of vertices is called even cycle, a cycle with an odd number of vertices is called odd cycle.Properties
A cycle 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.
- Any 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. More generally, a graph is bipartite if and only if it has no odd cycles as subgraphs.
- Cycles with an even number of vertices can be decomposed into a minimum of 2 independent sets (that is, [\alpha(n)=2]), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, [\alpha(n)=3]).
Directed cycle graph
A directed cyclic graph is a directed version of a cyclic graph, with all the edges being oriented in 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.
There is a directed cycle through any two vertices in a strongly connected component.
External link
- Eric W. Weisstein, [Cyclic Graph] at MathWorld.
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.