|
|
|
|
|
Cycle GraphIn the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. The circle graph with vertices is called . 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. 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.
- 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 (i.e. ), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (i.e. ).
See also References
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|