Cycle (graph Theory)

Cycle (graph Theory)

In graph theory, the term cycle may refer one of two types of specific cycles: a closed walk or simple path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle, or polygon. A cycle in a directed graph is called a directed cycle.

The term cycle may also refer to:

• An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycle, integral cycle, etc.
• An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.

Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.