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. [1] Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.
An n-vertex graph G is pancyclic if, for every in the range contains a cycle of length . [1] It is node-pancyclic or vertex-pancyclic if, for every vertex v and every k in the same range, it contains a cycle of length k that contains v. [2] Similarly, it is edge-pancyclic if, for every edge e and every k in the same range, it contains a cycle of length k that contains e. [2]
A bipartite graph cannot be pancyclic, because it does not contain any odd-length cycles, but it is said to be bipancyclic if it contains cycles of all even lengths from 4 to n. [3]
A maximal outerplanar graph is a graph formed by a simple polygon in the plane by triangulating its interior. Every maximal outerplanar graph is pancyclic, as can be shown by induction. The outer face of the graph is an n-vertex cycle, and removing any triangle connected to the rest of the graph by only one edge (a leaf of the tree that forms the dual graph of the triangulation) forms a maximal outerplanar graph on one fewer vertex, that by induction has cycles of all the remaining lengths. With more care in choosing which triangle to remove, the same argument shows more strongly that every maximal outerplanar graph is node-pancyclic. [4] The same holds for graphs that have a maximal outerplanar spanning subgraph, as do for instance the wheel graphs.
A maximal planar graph is a planar graph in which all faces, even the outer face, are triangles. A maximal planar graph is node-pancyclic if and only if it has a Hamiltonian cycle: [5] if it is not Hamiltonian, it is certainly not pancyclic, and if it is Hamiltonian, then the interior of the Hamiltonian cycle forms a maximal outerplanar graph on the same nodes, to which the previous argument for maximal outerplanar graphs can be applied. [6] For instance, the illustration shows the pancyclicity of the graph of an octahedron, a Hamiltonian maximal planar graph with six vertices. More strongly, by the same argument, if a maximal planar graph has a cycle of length k, it has cycles of all smaller lengths. [7]
Halin graphs are the planar graphs formed from a planar drawing of a tree that has no degree-two vertices, by adding a cycle to the drawing that connects all the leaves of the tree. Halin graphs are not necessarily pancyclic, but they are almost pancyclic in the sense that there is at most one missing cycle length. The length of the missing cycle is necessarily even. If none of the interior vertices of a Halin graph has degree three, then it is necessarily pancyclic. [8]
Bondy (1971) observed that many classical conditions for the existence of a Hamiltonian cycle were also sufficient conditions for a graph to be pancyclic, and on this basis conjectured that every 4-connected planar graph is pancyclic. However, Malkevitch (1971) found a family of counterexamples.
A tournament is a directed graph with one directed edge between each pair of vertices. Intuitively, a tournament can be used to model a round-robin sports competition, by drawing an edge from the winner to the loser of each game in the competition. A tournament is called strongly connected or strong if and only if it cannot be partitioned into two nonempty subsets L and W of losers and winners, such that every competitor in W beats every competitor in L. [9] Every strong tournament is pancyclic [10] and node-pancyclic. [11] If a tournament is regular (each competitor has the same number of wins and losses as each other competitor) then it is also edge-pancyclic; [12] however, a strong tournament with four vertices cannot be edge-pancyclic.
Mantel's theorem states that any n-vertex undirected graph with at least n2/4 edges, and no multiple edges or self-loops, either contains a triangle or it is the complete bipartite graph Kn/2,n/2. This theorem can be strengthened: any undirected Hamiltonian graph with at least n2/4 edges is either pancyclic or Kn/2,n/2. [1]
There exist n-vertex Hamiltonian directed graphs with n(n + 1)/2 − 3 edges that are not pancyclic, but every Hamiltonian directed graph with at least n(n + 1)/2 − 1 edges is pancyclic. Additionally, every n-vertex strongly connected directed graph in which each vertex has degree at least n (counting incoming and outgoing edges together) is either pancyclic or it is a complete bipartite directed graph. [13]
For any graph G, its kth power Gk is defined as the graph on the same vertex set that has an edge between every two vertices whose distance in G is at most k. If G is 2-vertex-connected, then by Fleischner's theorem its square G2 is Hamiltonian; this can be strengthened to show that it is necessarily vertex-pancyclic. [14] More strongly, whenever G2 is Hamiltonian, it is also pancyclic. [15]
It is NP-complete to test whether a graph is pancyclic, even for the special case of 3-connected cubic graphs, and it is also NP-complete to test whether a graph is node-pancyclic, even for the special case of polyhedral graphs. [16] It is also NP-complete to test whether the square of a graph is Hamiltonian, and therefore whether it is pancyclic. [17]
Pancyclicity was first investigated in the context of tournaments by Harary & Moser (1966), Moon (1966), and Alspach (1967). The concept of pancyclicity was named and extended to undirected graphs by Bondy (1971).
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
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 cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.
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 the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.
In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n – 1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n + 1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with sufficiently many edges must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of pairs of non-adjacent vertices: if every such pair has a sum that at least equals the total number of vertices in the graph, then the graph is Hamiltonian.
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.
In graph theory, a branch of mathematics, a Hamiltonian decomposition of a given graph is a partition of the edges of the graph into Hamiltonian cycles. Hamiltonian decompositions have been studied both for undirected graphs and for directed graphs. In the undirected case a Hamiltonian decomposition can also be described as a 2-factorization of the graph such that each factor is connected.
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.
In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.
In the mathematical field of graph theory, the Goldner–Harary graph is a simple undirected graph with 11 vertices and 27 edges. It is named after A. Goldner and Frank Harary, who proved in 1975 that it was the smallest non-Hamiltonian maximal planar graph. The same graph had already been given as an example of a non-Hamiltonian simplicial polyhedron by Branko Grünbaum in 1967.
In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.
In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
In graph theory and graph drawing, a subhamiltonian graph is a subgraph of a planar Hamiltonian graph.
