 Cycle graph

This article is about connected, 2regular graphs. For other uses, see Cycle graph (disambiguation).
Cycle graph
A cycle graph of length 6Vertices n Edges n Girth n Automorphisms 2n (D_{n}) Chromatic number 3 if n is odd
2 if n is evenChromatic index 3 if n is odd
2 if n is evenSpectral Gap Properties 2regular
Vertextransitive
Edgetransitive
Unit distance
Hamiltonian
EulerianNotation C_{n} v · 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 connected in a closed chain. The cycle graph with n vertices is called C_{n}. The number of vertices in C_{n} equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it. Contents
Terminology
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 ngon are also often used. 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:
 Connected
 2regular
 Eulerian
 Hamiltonian
 2vertex 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).
 2edge colorable, if and only if it has an even number of vertices
 3vertex colorable and 3edge colorable, for any number of vertices
 A unit distance graph
In addition:
 As cycle graphs can be drawn as regular polygons, the symmetries of an ncycle are the same as those of a regular polygon with n sides, the dihedral group of order 2n. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the ncycle is a symmetric graph.
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 indegree 1 and uniform outdegree 1.
Directed cycle graphs are Cayley graphs for cyclic groups (see e.g. Trevisan).
See also
External links
 Weisstein, Eric W., "Cycle Graph" from MathWorld. (discussion of both 2regular cycle graphs and the grouptheoretic concept of cycle diagrams)
 Luca Trevisan, Characters and Expansion.
Categories: Parametric families of graphs
 Regular graphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Cycle graph (algebra) — For other uses, see Cycle graph (disambiguation). In group theory, a sub field 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. For… … Wikipedia
Cycle (graph theory) — In graph theory, the term cycle may refer to a closed 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… … Wikipedia
Cycle graph (disambiguation) — A cycle graph or cyclic graph is a connected, 2 regular graph.Cycle graph or cyclic graph may also refer to: * Cycle graph (algebra), a diagram representing the cycles determined by taking powers of group elements * Circulant graph * A graph… … Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
Graph homomorphism — Not to be confused with graph homeomorphism. In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices. Contents 1… … Wikipedia
Cycle — Contents 1 Chemistry 2 Economics 3 Mathematics 4 Music … Wikipedia
Cycle (mathematics) — This article is about group theory. For cycles in homological algebra, see Chain complex#Fundamental terminology. For cycles in graph theory, see Cycle (graph theory). In mathematics, and in particular in group theory, a cycle is a permutation of … Wikipedia
Cycle double cover — Unsolved problems in mathematics Does every bridgeless graph have a multiset of cycles covering every edge exactly twice? … Wikipedia
Cycle space — This article is about a concept in graph theory. For space allocated to bicycles, see segregated cycle facilities. In graph theory, an area of mathematics, a cycle space is a vector space defined from an undirected graph; elements of the cycle… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
18+© Academic, 20002024 Contact us: Technical Support, Advertising
Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx.Share the article and excerpts
Cycle graph
 Cycle graph

This article is about connected, 2regular graphs. For other uses, see Cycle graph (disambiguation).
Cycle graph
A cycle graph of length 6Vertices n Edges n Girth n Automorphisms 2n (D_{n}) Chromatic number 3 if n is odd
2 if n is evenChromatic index 3 if n is odd
2 if n is evenSpectral Gap Properties 2regular
Vertextransitive
Edgetransitive
Unit distance
Hamiltonian
EulerianNotation C_{n}