Cubic Graph
   HOME

TheInfoList



OR:

In the
mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, a cubic graph is a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
in which all vertices have
degree Degree may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathemati ...
three. In other words, a cubic graph is a 3-
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 outdegre ...
. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...
.


Symmetry

In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.. Many well-known individual graphs are cubic and symmetric, including the
utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosophe ...
, the
Petersen graph In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
, 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. 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 In the mathematical field of graph theory, the Frucht graph is a cubic graph with 12 vertices, 18 edges, and no nontrivial symmetries. It was first described by Robert Frucht in 1939. The Frucht graph is a pancyclic, Halin graph with chromatic ...
is one of the five smallest cubic graphs without any symmetries: it possesses only a single graph automorphism, the identity automorphism.


Coloring and independent sets

According to Brooks' theorem every connected cubic graph other than the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
''K''4 has a vertex coloring with at most three colors. Therefore, every connected cubic graph other than ''K''4 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 In graph theory, an 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 ...
. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s. 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 In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...
, Tietze's graph, the Blanuša snarks, the flower snark, the
double-star snark In the mathematical field of graph theory, the double-star snark is a snark with 30 vertices and 45 edges. In 1975, Rufus Isaacs introduced two infinite families of snarks—the flower snark and the BDS snark, a family that includes the two B ...
, the
Szekeres snark In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973. As a snark, the Szekeres graph is a connected, bridgeless cubic graph wi ...
and the
Watkins snark In the mathematical field of graph theory, the Watkins snark is a snark with 50 vertices and 75 edges. It was discovered by John J. Watkins in 1989. As a snark, the Watkins graph is a connected, bridgeless cubic graph with chromatic index equal ...
. There is an infinite number of distinct snarks.


Topology and geometry

Cubic graphs arise naturally in
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ho ...
in several ways. For example, if one considers a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
to be a 1-dimensional
CW complex A CW complex (also called cellular complex or cell complex) is a kind of a topological space that is particularly important in algebraic topology. It was introduced by J. H. C. Whitehead (open access) to meet the needs of homotopy theory. This cla ...
, 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 In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs ( homeomorphic images of ,1/math> ...
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 A flag is a piece of fabric (most often rectangular or quadrilateral) with a distinctive design and colours. It is used as a symbol, a signalling device, or for decoration. The term ''flag'' is also used to refer to the graphic design emp ...
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.


Hamiltonicity

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 William Thomas Tutte Order of Canada, OC Royal Society, FRS Royal Society of Canada, FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian cryptanalysis, codebreaker and mathematician. During the Second World War, he made a brilliant a ...
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 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 conjec ...
.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976. Later,
Mark Ellingham Mark Norman Ellingham is a professor of mathematics at Vanderbilt University whose research concerns graph theory. With Joseph D. Horton, he is the discoverer and namesake of the Ellingham–Horton graphs, two cubic 3-vertex-connected bipartite g ...
constructed two more counterexamples: the
Ellingham–Horton graph 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. Elli ...
s.Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981..
Barnette's conjecture 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 ev ...
, 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. David Eppstein conjectured that every ''n''-vertex cubic graph has at most 2''n''/3 (approximately 1.260''n'') distinct Hamiltonian cycles, and provided examples of cubic graphs with that many cycles. The best proven estimate for the number of distinct Hamiltonian cycles is O(^n).


Other properties

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.082''n''. It is not known how to reduce this gap between this lower bound and the ''n''/6 upper bound.. It follows from the handshaking lemma, proven by
Leonhard Euler Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ma ...
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 In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
..
Lovász Lovász (): * Lázár Lovász (born 1942), a Hungarian athlete who competed in hammer throw * László Lovász (born 1948, Budapest), a mathematician, best known for his work in combinatorics, **Lovász conjecture (1970) ** Erdős–Faber–Lovász ...
and
Plummer Plummer may refer to: Places Communities *Plummer, Idaho, United States *Plummer, Indiana, United States *Plummer, Minnesota, United States *Plummer Additional, Ontario, Canada Buildings *Plummer Building, Rochester, Minnesota, United States * P ...
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..


Algorithms and complexity

Several researchers have studied the complexity of
exponential time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
algorithms restricted to cubic graphs. For instance, by applying
dynamic programming Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. I ...
to a path decomposition of the graph, Fomin and Høie showed how to find their maximum independent sets in time 2''n''/6 + o(''n''). The
travelling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
in cubic graphs can be solved in time O(1.2312''n'') and polynomial space.. Several important graph optimization problems are APX hard, meaning that, although they have
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solu ...
s whose
approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...
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 In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimiza ...
, maximum independent set, minimum
dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...
, and maximum cut. The crossing number (the minimum number of edges which cross in any graph drawing) of a cubic graph is also
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
for cubic graphs but may be approximated.. The
Travelling Salesman Problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
on cubic graphs has been proven to be
NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
to approximate to within any factor less than 1153/1152..


See also

* Table of simple cubic graphs


References


External links

* * *{{mathworld, urlname=CubicGraph, title=Cubic Graph Graph families Regular graphs