Barnette's conjecture

Last updated June 11, 2023

Unsolved problem in mathematics:

Is every cubic bipartite polyhedral graph Hamiltonian?

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.

Definitions

A planar graph is an undirected graph that can be embedded into the Euclidean plane without any 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 if its vertices can be colored with two different colors such that each edge has one endpoint of each color. A graph is cubic (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, 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

P. G.Tait ( 1884 ) conjectured that every cubic polyhedral graph is Hamiltonian; this came to be known as Tait's conjecture. It was disproven by W. T.Tutte ( 1946 ), 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.^[1]David W.Barnette ( 1969 ) 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

Kelmans (1994) ^[2] 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.^[3]

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.^[4]

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.^[5] 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.^[6] Another result was obtained by Alt et al. (2016): 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.

Notes

↑ Tutte (1971); Horton (1982).
↑ See Alt et al. (2016) for proofs
↑ Florek (2010).
↑ Holton, Manvel & McKay (1985); Hertel (2005).
↑ Feder & Subi (2006).
↑ Akiyama, Nishizeki & Saito (1980).
↑ Aldred et al. (2000).

Related Research Articles

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 (1884) and disproved by W. T. Tutte (1946), 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.

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

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.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

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.

In graph theory, a uniquely colorable graph is a $k$ -chromatic graph that has only one possible (proper) $k$ -coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into $k$ independent sets and there is no way to partition them into $k - 1$ independent sets.

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 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.

In the mathematical discipline of graph theory, the dual graph of a plane graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

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 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. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

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 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 the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.

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 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. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic polyhedral graph with no Hamiltonian cycle, the smallest such graph possible. It was discovered in the mid-1960s by Joshua Lederberg, David Barnette, and Juraj Bosák, after whom it is named. It has 38 vertices and 69 edges.

In the mathematical field of graph theory, the Walther graph, also called the Tutte fragment, is a planar bipartite graph with 25 vertices and 31 edges named after Hansjoachim Walther. It has chromatic index 3, girth 3 and diameter 8.

References

Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing , 3 (2): 73–76, MR 0596313
Alt, Helmut; Payne, Michael S.; Schmidt, Jens M.; Wood, David R. (2016), "Thoughts on Barnette's conjecture" (PDF), Australasian Journal of Combinatorics , 64 (2): 354–365, MR 3442496
Aldred, R. E. L.; Bau, S.; Holton, D. A.; McKay, Brendan D. (2000), "Nonhamiltonian 3-connected cubic planar graphs", SIAM Journal on Discrete Mathematics , 13 (1): 25–32, doi: 10.1137/S0895480198348665 , MR 1737931
Barnette, David W. (1969), "Conjecture 5", in Tutte, W. T. (ed.), Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, New York: Academic Press, MR 0250896
Feder, Tomas; Subi, Carlos (2006), On Barnette's conjecture, ECCC TR06-015
Florek, Jan (2010), "On Barnette's conjecture", Discrete Mathematics , 310 (10–11): 1531–1535, doi: 10.1016/j.disc.2010.01.018 , MR 2601261
Goodey, P. R. (1975), "Hamiltonian circuits in polytopes with even sided faces", Israel Journal of Mathematics , 22 (1): 52–56, doi: 10.1007/BF02757273 , MR 0410565
Hertel, Alexander (2005), A survey & strengthening of Barnette's conjecture (PDF)
Holton, D. A.; Manvel, B.; McKay, B. D. (1985), "Hamiltonian cycles in cubic 3-connected bipartite planar graphs", Journal of Combinatorial Theory, Series B, 38 (3): 279–297, doi: 10.1016/0095-8956(85)90072-3 , MR 0796604
Horton, J. D. (1982), "On two-factors of bipartite regular graphs", Discrete Mathematics , 41 (1): 35–41, doi: 10.1016/0012-365X(82)90079-6 , MR 0676860
Kardoš, F. (2020), "A computer-assisted proof of the Barnette-Goodey Conjecture: not only fullerene graphs are hamiltonian", SIAM Journal on Discrete Mathematics , 34 (1): 62–100, arXiv: 1409.2440 , doi:10.1137/140984737, S2CID 119660011
Kelmans, A. K. (1994), "Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles", in Kelmans, A. K. (ed.), Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar 1972–1990, American Mathematical Society Translations, Series 2, vol. 158, pp. 127–140
Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine , 5th Series, 17: 30–46; Reprinted in Scientific Papers, Vol. II, pp. 85–98
Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society , 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98
Tutte, W. T. (1971), "On the 2-factors of bicubic graphs", Discrete Mathematics , 1 (2): 203–208, doi: 10.1016/0012-365X(71)90027-6 , MR 0291010

External links

Weisstein, Eric W., "Barnette's Conjecture", MathWorld
Barnette's Conjecture in the Open Problem Garden, Robert Samal, 2007.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Tutte (1971); Horton (1982).

[2] See Alt et al. (2016) for proofs

[FOOTNOTEFlorek2010-3] Florek (2010).

[4] Holton, Manvel & McKay (1985); Hertel (2005).

[5] Feder & Subi (2006).

[6] Akiyama, Nishizeki & Saito (1980).

[7] Aldred et al. (2000).

[1]

[2]

[3]

[4]

[5]

[6]

[7]