graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a cycle graph or circular graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is

simple Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by John ...

) connected in a closed chain. The cycle graph with vertices is called . The number of vertices in equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it. If

n = 1

, it is an isolated loop.

Terminology

There are many

synonym A synonym is a word, morpheme, or phrase that means precisely or nearly the same as another word, morpheme, or phrase in a given language. For example, in the English language, the words ''begin'', ''start'', ''commence'', and ''initiate'' are a ...

s for "cycle graph". These include simple cycle graph and cyclic graph, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, cycle, polygon, or ''n''-gon are also often used. The term ''n''-cycle is sometimes used in other settings. A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle.

Properties

A cycle graph is: * 2-edge colorable, if and only if it has an even number of vertices * 2-regular * 2-vertex colorable, if and only if it has an even number of vertices. More generally, a graph is bipartite

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

it has no odd cycles ( Kőnig, 1936). * Connected * Eulerian *

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

* A unit distance graph In addition: *As cycle graphs can be drawn as

regular polygon In Euclidean geometry, a regular polygon is a polygon that is Equiangular polygon, direct equiangular (all angles are equal in measure) and Equilateral polygon, equilateral (all sides have the same length). Regular polygons may be either ''convex ...

s, the symmetries of an ''n''-cycle are the same as those of a regular polygon with ''n'' sides, the

dihedral group In mathematics, a dihedral group is the group (mathematics), group of symmetry, symmetries of a regular polygon, which includes rotational symmetry, rotations and reflection symmetry, reflections. Dihedral groups are among the simplest example ...

of order 2''n''. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the ''n''-cycle is a symmetric graph. Similarly to the Platonic graphs, the cycle graphs form the skeletons of the dihedra. Their duals are the

dipole graph In graph theory, a dipole graph, dipole, bond graph, or linkage, is a multigraph consisting of two vertex (graph theory), vertices connected with a number of Multiple edges, parallel edges. A dipole graph containing edges is called the dipole ...

s, which form the skeletons of the hosohedra.

Directed cycle graph

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the 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. A directed cycle graph has uniform in-degree 1 and uniform out-degree 1. Directed cycle graphs are

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a Graph (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

s for

cyclic group In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...

s (see e.g. Trevisan).

References

Sources

External links