All Topics  
Cycle graph

 

 
   Email Print
   Bookmark   Link
 

 

Cycle graph
 
 
  Topics Cycle graph Topic Home

In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, a cycle graph is a graph
Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
 that consists of a single cycle
Path (graph theory)

In graph theory, a path in a graph is a sequence of vertex such that from each of its vertices there is an edge to the next vertex in the sequence....
, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in a Cn equals the number of edges, and every vertex has degree
Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
 2; that is, every vertex has exactly two edges incident with it.

e are many synonym
Synonym

Synonyms are different words with identical or very similar meanings. Words that are synonyms are said to be synonymous, and the state of being a synonym is called synonymy....
s for "cycle graph".






Discussion
Ask a question about 'Cycle graph'
Start a new discussion about 'Cycle graph'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, a cycle graph is a graph
Graph (mathematics)

In mathematics a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges....
 that consists of a single cycle
Path (graph theory)

In graph theory, a path in a graph is a sequence of vertex such that from each of its vertices there is an edge to the next vertex in the sequence....
, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn. The number of vertices in a Cn equals the number of edges, and every vertex has degree
Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edge incidence to the vertex. The degree of a vertex is denoted The maximum degree of a graph G, denoted by ?, is the maximum degree of its vertices, and the minimum degree of a graph, denoted by d, is the minimum degree of its vertices....
 2; that is, every vertex has exactly two edges incident with it.

Terminology

There are many synonym
Synonym

Synonyms are different words with identical or very similar meanings. Words that are synonyms are said to be synonymous, and the state of being a synonym is called synonymy....
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. 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
  • 2-regular
    Regular graph

    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i.e. every vertex has the same Degree or valency....
  • Eulerian
  • Hamiltonian
  • 2-vertex colorable
    Bipartite

    Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:* 2 In mathematics:...
    , if and only if it has an even number of vertices. More generally, a graph is bipartite if and only if
    If and only if

    If and only if, in logic and fields that rely on it such as mathematics and philosophy, is a biconditional logical connective between statements....
     it has no odd cycles (Konig, 1936).
  • 2-edge colorable, if and only if it has an even number of vertices
  • 3-vertex colorable and 3-edge colorable, for any number of vertices
  • A unit distance graph
    Unit distance graph

    In mathematics, and 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 by an edge whenever the distance between the two points is exactly one....


In addition:
  • As cycle graphs can be drawn
    Graph drawing

    Graph drawing, as a branch of graph theory, applies topology and geometry to derive two-dimensional representations of graph s. Graph drawing is motivated by applications such as Very-large-scale integration, social network analysis, cartography, and bioinformatics....
     as regular polygon
    Regular polygon

    A regular polygon is a polygon which is Equiangular polygon and equilateral . Regular polygons may be convex or Star polygon....
    s, the symmetries of an     n-cycle are the same as those of a regular polygon with n sides, the dihedral group
    Dihedral group

    In mathematics, a dihedral group is the group of symmetry of a regular polygon, including both rotational symmetry and reflection symmetry. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry....
     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
    Symmetric graph

    In graph theory, a graph is symmetric if it is both Vertex-transitive graph and Edge-transitive graph. Symmetric graphs are regular graph.Every cycle graph and complete graph is symmetric....
    .


Directed cycle graph

Dc8
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
Directed graph

A directed graph or digraph is a pair G= of:* a Set V, whose element are called vertices or nodes,* a set A of ordered pairs of vertices, called arcs, directed edges, or arrows....
, a set of edges which contains at least one edge (or arc) from each directed cycle is called a feedback arc set
Feedback arc set

In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph ....
. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set
Feedback vertex set

In computational complexity theory, the feedback vertex set problem is a graph theory NP-complete problem. It was among the Karp's 21 NP-complete problems....
.

A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.

Directed cycle graphs are Cayley graph
Cayley graph

In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph theory that encodes the structure of a discrete group....
s for cyclic group
Cyclic group

In group theory, a cyclic group or monogenous group is a group that can be generating set of a group by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g ....
s (see e.g. Trevisan).

See also

  • Complete bipartite graph
    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....
  • Path graph
    Path graph

    In the Mathematics field of graph theory, a path graph is a particularly simple example of a tree , namely one which is not branched at all, that is, contains only nodes of degree two and one....
  • Complete graph
    Complete graph

    In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
  • Null graph
    Null graph

    The null graph or the empty graph is either the graph with no vertices and no edges, or any graph with no edges.The null graph is the initial object in the category of graphs, according to some definitions of a category of graphs....


External links

  • Eric W. Weisstein, at MathWorld
    MathWorld

    MathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by Wolfram Research Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at Urbana-Champaign....
    . (MathWorld discusses both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams in the same article.)


  • Luca Trevisan
    Luca Trevisan

    Luca Trevisan is an associate professor of computer science at the University of California, Berkeley.His research area is theoretical computer science, focusing on randomness, cryptography, PCP s, approximation, property testing, and sublinear algorithms....
    , .