In
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a cycle graph or circular graph is a
graph 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 Johnn ...
) connected in a closed chain. The cycle graph with vertices is called . The number of vertices in equals the number of
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed ...
s, and every vertex has
degree 2; that is, every vertex has exactly two edges incident with it.
Terminology
There are many
synonym
A synonym is a word, morpheme, or phrase that means exactly 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 al ...
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" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
it has no odd cycles (
Kőnig, 1936).
*
Connected
*
Eulerian
*
Hamiltonian
* A
unit distance graph
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these grap ...
In addition:
*As cycle graphs can be
drawn as
regular polygon
In Euclidean geometry, a regular polygon is a polygon that is direct equiangular (all angles are equal in measure) and equilateral (all sides have the same length). Regular polygons may be either convex, star or skew. In the limit, a sequence ...
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 of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, ...
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 graphs, 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
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
, 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 that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
s for
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
s (see e.g. Trevisan).
See also
*
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
*
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
*
Circulant graph
In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.
Equivalent definitions
Cir ...
*
Cycle graph (algebra)
In group theory, a subfield of abstract algebra, a group cycle graph illustrates the various cycles of a group and is particularly useful in visualizing the structure of small finite groups.
A cycle is the set of powers of a given group elemen ...
*
Null graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is th ...
*
Path graph
References
Sources
*
External links
*{{MathWorld , urlname=CycleGraph , title=Cycle Graph (discussion of both 2-regular cycle graphs and the group-theoretic concept of
cycle diagrams)
*
Luca Trevisan
Luca Trevisan (21 July 1971) is an Italian professor of computer science at Bocconi University in Milan.
His research area is theoretical computer science, focusing on randomness, cryptography, probabilistically checkable proofs, approximation ...
Characters and Expansion
Parametric families of graphs
Regular graphs