Cycle graph

From Psychology Wiki

Community portal · Tasks to do · News · Help

Clinical · Educational · Ind&Org · Other fields · Professional · Transpersonal · World

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language
Personality | Philosophy | Research Methods | Social | Statistics

Psychology: Debates · Journals · Psychologists

---

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.

Contents 1 A note on terminology 2 Properties 3 Directed cycle graph 4 External link

[edit] 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.

[edit] 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.
• A unit distance graph

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, ), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (that is, ).

[edit] 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.

[edit] External link

• Eric W. Weisstein, Cyclic Graph at MathWorld.cs:Kružnice_(graf)

This page uses content from the English-language version of Wikipedia. The original article was at Cycle graph. The list of authors can be seen in the page history. As with Psychology Wiki, the text of Wikipedia is available under the GNU Free Documentation License.