Cycle graph
From Free net encyclopedia
←Older revision | Newer revision→
Disambiguation: "Cycle graph" can have several meanings, this article is about regular graphs of degree 2, i.e. polygons. Please see cycle graph (disambiguation) for others.
Image:C6graph.png 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 <math>n</math> vertices is called <math>C_n</math>. The number of vertices in a <math>C_n</math> equals the number of edges, and every vertex has degree two, that is, every vertex has exactly two edges incident with it.
Contents |
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.
In addition:
- 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, <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>).
Directed cycle graph
Image:DC8.png 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.cs:Kružnice_(graf)