HOME

TheInfoList



OR:

Barnette's conjecture is an
unsolved problem List of unsolved problems may refer to several notable conjectures or open problems in various academic fields: Natural sciences, engineering and medicine * Unsolved problems in astronomy * Unsolved problems in biology * Unsolved problems in chem ...
in graph theory, a branch of
mathematics 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 ...
, concerning Hamiltonian cycles in graphs. It is named after
David W. Barnette David (; , "beloved one") (traditional spelling), , ''Dāwūd''; grc-koi, Δαυΐδ, Dauíd; la, Davidus, David; gez , ዳዊት, ''Dawit''; xcl, Դաւիթ, ''Dawitʿ''; cu, Давíдъ, ''Davidŭ''; possibly meaning "beloved one". w ...
, a professor emeritus at the University of California, Davis; it states that every
bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
polyhedral graph with three edges per vertex has a Hamiltonian cycle.


Definitions

A
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. In other words, it can be drawn in such a way that no edges cross ...
is an undirected graph that can be embedded into the
Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
without any
crossings Crossings may refer to: * ''Crossings'' (Buffy novel), a 2002 original novel based on the U.S. television series ''Buffy the Vampire Slayer'' * Crossings (game), a two-player abstract strategy board game invented by Robert Abbott * ''Crossings'' ...
. A planar graph is called polyhedral if and only if it is 3-vertex-connected, that is, if there do not exist two vertices the removal of which would disconnect the rest of the graph. A graph is
bipartite Bipartite may refer to: * 2 (number) * Bipartite (theology), a philosophical term describing the human duality of body and soul * Bipartite graph, in mathematics, a graph in which the vertices are partitioned into two sets and every edge has an en ...
if its vertices can be colored with two different colors such that each edge has one endpoint of each color. A graph is
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
(or 3-regular) if each vertex is the endpoint of exactly three edges. Finally, a graph is Hamiltonian if there exists a cycle that passes through each of its vertices exactly once. Barnette's conjecture states that every cubic bipartite polyhedral graph is Hamiltonian. By
Steinitz's theorem 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 grap ...
, a planar graph represents the edges and vertices of a convex polyhedron if and only if it is polyhedral. A three-dimensional polyhedron has a cubic graph if and only if it is a simple polyhedron. And, a planar graph is bipartite if and only if, in a planar embedding of the graph, all face cycles have even length. Therefore, Barnette's conjecture may be stated in an equivalent form: suppose that a three-dimensional simple convex polyhedron has an even number of edges on each of its faces. Then, according to the conjecture, the graph of the polyhedron has a Hamiltonian cycle.


History

conjectured that every cubic polyhedral graph is Hamiltonian; this came to be known as Tait's conjecture. It was disproven by , who constructed a counterexample with 46 vertices; other researchers later found even smaller counterexamples. However, none of these known counterexamples is bipartite. Tutte himself conjectured that every cubic 3-connected bipartite graph is Hamiltonian, but this was shown to be false by the discovery of a counterexample, 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 conject ...
. proposed a weakened combination of Tait's and Tutte's conjectures, stating that every bipartite cubic polyhedron is Hamiltonian, or, equivalently, that every counterexample to Tait's conjecture is non-bipartite.


Equivalent forms

showed that Barnette's conjecture is equivalent to a superficially stronger statement, that for every two edges ''e'' and ''f'' on the same face of a bipartite cubic polyhedron, there exists a Hamiltonian cycle that contains ''e'' but does not contain ''f''. Clearly, if this statement is true, then every bipartite cubic polyhedron contains a Hamiltonian cycle: just choose ''e'' and ''f'' arbitrarily. In the other directions, Kelmans showed that a counterexample could be transformed into a counterexample to the original Barnette conjecture. Barnette's conjecture is also equivalent to the statement that the vertices of the dual of every cubic bipartite polyhedral graph can be partitioned into two subsets whose induced subgraphs are trees. The cut induced by such a partition in the dual graph corresponds to a Hamiltonian cycle in the primal graph.


Partial results

Although the truth of Barnette's conjecture remains unknown, computational experiments have shown that there is no counterexample with fewer than 86 vertices. If Barnette's conjecture turns out to be false, then it can be shown to be NP-complete to test whether a bipartite cubic polyhedron is Hamiltonian. If a planar graph is bipartite and cubic but only of connectivity 2, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs. Another result was obtained by : if the dual graph can be vertex-colored with colors blue, red and green such that every red-green cycle contains a vertex of degree 4, then the primal graph is Hamiltonian.


Related problems

A related conjecture of Barnette states that every cubic polyhedral graph in which all faces have six or fewer edges is Hamiltonian. Computational experiments have shown that, if a counterexample exists, it would have to have more than 177 vertices.. The conjecture was proven by . The intersection of these two conjectures would be that every bipartite cubic polyhedral graph in which all faces have four or six edges is Hamiltonian. This was proved to be true by .


Notes


References

* * * * * * * * * * * * *; Reprinted in ''Scientific Papers'', Vol. II, pp. 85–98 * *


External links

*{{mathworld, title=Barnette's Conjecture, urlname=BarnettesConjecture, mode=cs2
Barnette's Conjecture
in the Open Problem Garden, Robert Samal, 2007. Conjectures Unsolved problems in graph theory Planar graphs Hamiltonian paths and cycles