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.
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.[7]
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 Goodey (1975).
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).
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
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, 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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
