Cycle graph | |
---|---|

A cycle graph of length 6 | |

Vertices | n |

Edges | n |

Girth | n |

Automorphisms | 2n (D)_{n} |

Chromatic number | 3 if n is odd2 otherwise |

Chromatic index | 3 if n is odd2 otherwise |

Spectrum | {2 cos(2kπ/n); k = 1, ..., n} ^{ [1] } |

Properties | 2-regular Vertex-transitive Edge-transitive Unit distance Hamiltonian Eulerian |

Notation | |

Table of graphs and parameters |

In graph theory, 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) connected in a closed chain. The cycle graph with *n* vertices is called *C _{n}*. The number of vertices in

There are many synonyms 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

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

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 it has no odd cycles (Kőnig, 1936).
- Connected
- Eulerian
- Hamiltonian
- A unit distance graph

In addition:

- As cycle graphs can be drawn as regular polygons, the symmetries of an
*n*-cycle are the same as those of a regular polygon with*n*sides, the dihedral group 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.

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 graphs for cyclic groups (see e.g. Trevisan).

Wikimedia Commons has media related to . Cycle graphs |

In graph theory, a **cycle** in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. A **directed cycle** in a directed graph is a non-empty directed trail in which the only repeated vertices are the first and last vertices.

In the mathematical field of graph theory, a **bipartite graph** is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . Vertex sets and are usually called the *parts* of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

In the mathematical field of graph theory, a **Hamiltonian path** is a path in an undirected or directed graph that visits each vertex exactly once. A **Hamiltonian cycle** is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

This is a **glossary of graph theory terms**. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

In graph theory, an **Eulerian trail** is a trail in a finite graph that visits every edge exactly once. Similarly, an **Eulerian circuit** or **Eulerian cycle** is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this:

In the mathematical discipline of graph theory, the **line graph** of an undirected graph *G* is another graph L(*G*) that represents the adjacencies between edges of *G*. L(*G*) is constructed in the following way: for each edge in *G*, make a vertex in L(*G*); for every two edges in *G* that have a vertex in common, make an edge between their corresponding vertices in L(*G*).

In graph theory, an **edge coloring** of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The **edge-coloring problem** asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the **chromatic index** of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In geometry, a **cross-polytope**, **hyperoctahedron**, **orthoplex**, or **cocube** is a regular, convex polytope that exists in *n*-dimensions. A 2-dimensional cross-polytope is a square, a 3-dimensional cross-polytope is a regular octahedron, and a 4-dimensional cross-polytope is a 16-cell. Its facets are simplexes of the previous dimension, while the cross-polytope's vertex figure is another cross-polytope from the previous dimension.

In the mathematical field of graph theory, a **cubic graph** is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called **trivalent graphs**.

In graph theory, the **degree** of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The **maximum degree** of a graph , denoted by , and the **minimum degree** of a graph, denoted by , are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0.

In the mathematical field of graph theory, the **Desargues graph** is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In graph theory, a **factor** of a graph *G* is a spanning subgraph, i.e., a subgraph that has the same vertex set as *G*. A ** k-factor** of a graph is a spanning

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.

Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.

In graph theory, a **rook's graph** is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

A **thrackle** is an embedding of a graph in the plane, such that each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, the crossing must be *transverse*.

In graph theory, a branch of mathematics, a **skew-symmetric graph** is a directed graph that is isomorphic to its own transpose graph, the graph formed by reversing all of its edges, under an isomorphism that is an involution without any fixed points. Skew-symmetric graphs are identical to the double covering graphs of bidirected graphs.

In the mathematical field of graph theory, the **odd graphs***O _{n}* are a family of symmetric graphs with high odd girth, defined from certain set systems. They include and generalize the Petersen graph.

In the mathematical study of graph theory, a **pancyclic graph** is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In the mathematical field of graph theory, a **prism graph** is a graph that has one of the prisms as its skeleton.

- ↑ Some simple graph spectra. win.tue.nl
- ↑ "Problem 11707".
*Amer. Math. Monthly*.**120**(5): 469–476. May 2013. doi:10.4169/amer.math.monthly.120.05.469. JSTOR 10.4169/amer.math.monthly.120.05.469.

- Weisstein, Eric W. "Cycle Graph".
*MathWorld*. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams) - Luca Trevisan, Characters and Expansion.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.