# Cycle graph

*34,146*pages on

this wiki

## Redirected from Directed cycle

Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language |
Individual differences |
Personality |
Philosophy |
Social |

Methods |
Statistics |
Clinical |
Educational |
Industrial |
Professional items |
World psychology |

**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

[show]## 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**.

## PropertiesEdit

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, ).

## 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.

## External linkEdit

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

This page uses Creative Commons Licensed content from Wikipedia (view authors). |