Concept
Cycle graph
Related concepts (26)
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"). The order-zero graph, K_0, is the unique graph having no vertices (hence its order is zero). It follows that K_0 also has no edges. Thus the null graph is a regular graph of degree zero. Some authors exclude K_0 from consideration as a graph (either by definition, or more simply as a matter of convenience).
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. Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher.
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. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‐regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.
Symmetric graph
In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u_1—v_1 and u_2—v_2 of G, there is an automorphism such that and In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive. By definition (ignoring u_1 and u_2), a symmetric graph without isolated vertices must also be vertex-transitive.
Complement graph
In the mathematical field of graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. The complement is not the set complement of the graph; only the edges are complemented. Let G = (V, E) be a simple graph and let K consist of all 2-element subsets of V.
Cycle (graph theory)
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree. A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).
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 Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.
NP-completeness
In computational complexity theory, a problem is NP-complete when: It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no". When the answer is "yes", this can be demonstrated through the existence of a short (polynomial length) solution. The correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
Eulerian path
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). 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: Given the graph in the image, is it possible to construct a path (or a cycle; i.
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. Circulant graphs can be described in several equivalent ways: The automorphism group of the graph includes a cyclic subgroup that acts transitively on the graph's vertices. In other words, the graph has a graph automorphism, which is a cyclic permutation of its vertices.