This article is about connected, 2-regular graphs. For other uses, see Cyclic graph.
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 Cn.[2] The number of vertices in Cn equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.
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 n-cycle is sometimes used in other settings.[3]
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.
Propertiesedit
A cycle graph is:
2-edge colorable, if and only if it has an even number of vertices
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).
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 2n. 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.
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.
cycle, graph, this, article, about, connected, regular, graphs, other, uses, cyclic, graph, graph, theory, cycle, graph, circular, graph, graph, that, consists, single, cycle, other, words, some, number, vertices, least, graph, simple, connected, closed, chain. This article is about connected 2 regular graphs For other uses see Cyclic graph 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 Cn 2 The number of vertices in Cn equals the number of edges and every vertex has degree 2 that is every vertex has exactly two edges incident with it CycleGirthnAutomorphisms2n Dn Chromatic number3 if n is odd2 otherwiseChromatic index3 if n is odd2 otherwiseSpectrum 2cos 2kpn k 1 n displaystyle left 2 cos left frac 2k pi n right k 1 cdots n right 1 Properties2 regularVertex transitiveEdge transitiveUnit distanceHamiltonianEulerianNotationCnTable of graphs and parameters Contents 1 Terminology 2 Properties 3 Directed cycle graph 4 See also 5 References 6 Sources 7 External linksTerminology editThere 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 n cycle is sometimes used in other settings 3 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 editA 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 Konig 1936 Connected Eulerian Hamiltonian A unit distance graphIn 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 2n 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 edit nbsp A directed cycle graph of length 8A 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 See also edit nbsp Wikimedia Commons has media related to Cycle graphs Complete bipartite graph Complete graph Circulant graph Cycle graph algebra Null graph Path graphReferences edit Some simple graph spectra win tue nl Diestel 2017 p 8 1 3 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 S2CID 41161918 Sources editDiestel Reinhard 2017 Graph Theory 5 ed Springer ISBN 978 3 662 53621 6 External links editWeisstein 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 Retrieved from https en wikipedia org w index php title Cycle graph amp oldid 1111132820, wikipedia, wiki, book, books, library,
