Pancyclic graph
Encyclopedia
In the mathematical study of graph theory
, a pancyclic graph is a directed or undirected graph that contains cycles
of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.
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.
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.
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: 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 planar graphs can be applied. 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.
Halin graph
s 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.
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, found a family of counterexamples.
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 subsets L and W of losers and winners, such that every competitor in W beats every competitor in L. Every strong tournament is pancyclic and node-pancyclic. 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; however, a strong tournament with four vertices cannot be edge-pancyclic.
Kn/2,n/2. This theorem can be strengthened: any undirected graph with at least n2/4 edges is either pancyclic or Kn/2,n/2.
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 graph in which each edge has degree at least n (counting incoming and outgoing edges together) is either pancyclic or it is a complete bipartite graph.
to test whether a graph is pancyclic, even for the special case of 3-connected
cubic graph
s, and it is also NP-complete to test whether a graph is node-pancyclic, even for the special case of polyhedral graph
s.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a pancyclic graph is a directed or undirected graph that contains cycles
Cycle 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 connected in a closed chain. The cycle graph with n vertices is called Cn...
of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.
Definitions
An n-vertex graph G is pancyclic if, for every k in the range , G contains a cycle of length k. 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. 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.A bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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.
Planar graphs
A maximalMaximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
outerplanar graph
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
is a graph formed by a simple polygon
Simple polygon
In geometry, a simple polygon is a closed polygonal chain of line segments in the plane which do not have points in common other than the common vertices of pairs of consecutive segments....
in the plane by triangulating
Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
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
Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
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.
A maximal planar graph
Planar graph
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...
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: 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 planar graphs can be applied. For instance, the illustration shows the pancyclicity of the graph of an octahedron
Octahedron
In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....
, 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.
Halin graph
Halin graph
In graph theory, a mathematical discipline, a Halin graph is a planar graph constructed from a plane embedding of a tree with at least four vertices and with no vertices of degree 2, by connecting all the leaves of the tree with a cycle that passes around the tree in the natural cyclic order...
s are the planar graphs formed from a planar drawing of a tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is 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.
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, found a family of counterexamples.
Tournaments
A tournamentTournament (graph theory)
A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge....
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
Round-robin tournament
A round-robin tournament is a competition "in which each contestant meets all other contestants in turn".-Terminology:...
, 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 subsets L and W of losers and winners, such that every competitor in W beats every competitor in L. Every strong tournament is pancyclic and node-pancyclic. If a tournament is 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. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
(each competitor has the same number of wins and losses as each other competitor) then it is also edge-pancyclic; however, a strong tournament with four vertices cannot be edge-pancyclic.
Graphs with many edges
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 graphComplete 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.- Definition :...
Kn/2,n/2. This theorem can be strengthened: any undirected graph with at least n2/4 edges is either pancyclic or Kn/2,n/2.
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 graph in which each edge has degree at least n (counting incoming and outgoing edges together) is either pancyclic or it is a complete bipartite graph.
Computational complexity
It is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
to test whether a graph is pancyclic, even for the special case of 3-connected
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
cubic graph
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
s, and it is also NP-complete to test whether a graph is node-pancyclic, even for the special case of polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
s.