Ad blocker interference detected!
Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers
Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.
Individual differences |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |
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 vertices is called . The number of vertices in a 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 terminologyEdit
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.
A cycle graph is:
- 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.
- A unit distance graph
- 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, ), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, ).
Directed cycle graph Edit
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.
|This page uses Creative Commons Licensed content from Wikipedia (view authors).|