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.
A bicubic graph is a cubic bipartite graph.
In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census. [1] Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number s such that each two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph. He showed that s is at most 5, and provided examples of graphs with each possible value of s from 1 to 5. [2]
Semi-symmetric cubic graphs include the Gray graph (the smallest semi-symmetric cubic graph), the Ljubljana graph, and the Tutte 12-cage.
The Frucht graph is one of the five smallest cubic graphs without any symmetries: [3] it possesses only a single graph automorphism, the identity automorphism. [4]
According to Brooks' theorem every connected cubic graph other than the complete graph K4 has a vertex coloring with at most three colors. Therefore, every connected cubic graph other than K4 has an independent set of at least n/3 vertices, where n is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.
According to Vizing's theorem every cubic graph needs either three or four colors for an edge coloring. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. By Kőnig's line coloring theorem every bicubic graph has a Tait coloring.
The bridgeless cubic graphs that do not have a Tait coloring are known as snarks. They include the Petersen graph, Tietze's graph, the Blanuša snarks, the flower snark, the double-star snark, the Szekeres snark and the Watkins snark. There is an infinite number of distinct snarks. [5]
Cubic graphs arise naturally in topology in several ways. For example, the cubic graphs with 2g-2 vertices describe the different ways of cutting a surface of genus g ≥ 2 into pairs of pants. If one considers a graph to be a 1-dimensional CW complex, cubic graphs are generic in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are also formed as the graphs of simple polyhedra in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex.
An arbitrary graph embedding on a two-dimensional surface may be represented as a cubic graph structure known as a graph-encoded map. In this structure, each vertex of a cubic graph represents a flag of the embedding, a mutually incident triple of a vertex, edge, and face of the surface. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple and leaving the other two members unchanged. [6]
There has been much research on Hamiltonicity of cubic graphs. In 1880, P.G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture, the 46-vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian. However, Joseph Horton provided a counterexample on 96 vertices, the Horton graph. [7] Later, Mark Ellingham constructed two more counterexamples: the Ellingham–Horton graphs. [8] [9] Barnette's conjecture, a still-open combination of Tait's and Tutte's conjecture, states that every bicubic polyhedral graph is Hamiltonian. When a cubic graph is Hamiltonian, LCF notation allows it to be represented concisely.
If a cubic graph is chosen uniformly at random among all n-vertex cubic graphs, then it is very likely to be Hamiltonian: the proportion of the n-vertex cubic graphs that are Hamiltonian tends to one in the limit as n goes to infinity. [10]
David Eppstein conjectured that every n-vertex cubic graph has at most 2n/3 (approximately 1.260n) distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. [11] The best proven estimate for the number of distinct Hamiltonian cycles is . [12]
What is the largest possible pathwidth of an -vertex cubic graph?
The pathwidth of any n-vertex cubic graph is at most n/6. The best known lower bound on the pathwidth of cubic graphs is 0.082n. It is not known how to reduce this gap between this lower bound and the n/6 upper bound. [13]
It follows from the handshaking lemma, proven by Leonhard Euler in 1736 as part of the first paper on graph theory, that every cubic graph has an even number of vertices.
Petersen's theorem states that every cubic bridgeless graph has a perfect matching. [14] Lovász and Plummer conjectured that every cubic bridgeless graph has an exponential number of perfect matchings. The conjecture was recently proved, showing that every cubic bridgeless graph with n vertices has at least 2n/3656 perfect matchings. [15]
Several researchers have studied the complexity of exponential time algorithms restricted to cubic graphs. For instance, by applying dynamic programming to a path decomposition of the graph, Fomin and Høie showed how to find their maximum independent sets in time 2n/6 + o(n). [13] The travelling salesman problem in cubic graphs can be solved in time O(1.2312n) and polynomial space. [16] [17]
Several important graph optimization problems are APX hard, meaning that, although they have approximation algorithms whose approximation ratio is bounded by a constant, they do not have polynomial time approximation schemes whose approximation ratio tends to 1 unless P=NP. These include the problems of finding a minimum vertex cover, maximum independent set, minimum dominating set, and maximum cut. [18] The crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is also NP-hard for cubic graphs but may be approximated. [19] The Travelling Salesman Problem on cubic graphs has been proven to be NP-hard to approximate to within any factor less than 1153/1152. [20]
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
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, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.
In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.
In the mathematical field of graph theory, a quartic graph is a graph where all vertices have degree 4. In other words, a quartic graph is a 4-regular graph.
In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.
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 the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.
In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.
In the mathematical field of graph theory, the Ellingham–Horton graphs are two 3-regular graphs on 54 and 78 vertices: the Ellingham–Horton 54-graph and the Ellingham–Horton 78-graph. They are named after Joseph D. Horton and Mark N. Ellingham, their discoverers. These two graphs provide counterexamples to the conjecture of W. T. Tutte that every cubic 3-connected bipartite graph is Hamiltonian. The book thickness of the Ellingham-Horton 54-graph and the Ellingham-Horton 78-graph is 3 and the queue numbers 2.
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.
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.
In the mathematical discipline of graph theory, Petersen's theorem, named after Julius Petersen, is one of the earliest results in graph theory and can be stated as follows:
Petersen's Theorem. Every cubic, bridgeless graph contains a perfect matching.
The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.
