Open for Discovery

Location：Home / Journals / Article Detail

Journal of Applied Mathematics and Computation

DOI：http://dx.doi.org/10.26855/jamc.2023.06.012

PDF Download

A Note on Barnette’s Conjecture

Zijun Xiao

School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui, China.

*Corresponding author: Zijun Xiao

Date: July 31,2023　Hits: 336

Abstract

In 1969, Barnette conjectured that every 3-connected cubic planar bipartite graph is Hamiltonian. We obtain two results to help under-stand Barnette’s conjecture. The first result is inspired by the generation theorem of 3-connected cubic planar bipartite graphs, which is the work of Holton, Manvel and McKay. We define two operations called VO and EOR and prove that all graphs which are generated by the two operations from a unique graph of order 8 are Hamiltonian. We deduce also an equivalent description for the 3-connectivity of simple cubic plane bipartite graphs by the recent research hotspots of quasi spanning tree of faces. We prove that every simple cubic plane bipartite graph G is 3-connected if and only if the contraction graph HR(G) is 2-connected and 3-edge-connected, which meaning that if every 2-connected, 3-edge-connected planar graph of whose all vertex degrees are even and more than four has one quasi spanning tree of faces, then every 3-connected cubic planar bipartite graph is Hamiltonian.

References

[1] Tait, P. G., Listing’s Topologie, Philosophical Magazine, 5th Series, 1884, 17: 30–46.

[2] TuGe, W. T., On Hamiltonian circuits, Journal of the London Mathematical Society, 1946, 21 (2): 98–101.

[3] David W. BarneGe, Conjecture 5, Recent progress in combinatorics, Academic Press, New York, 1969, 343.

[4] H. Whitney, Coqcruent graphs and the connectivity of graphs, Am. J. Math., 1932,54 150-168.

[5] Goodey, P. R., Hamiltonian circuits in polytopes with even sided faces, Israel Journal of Mathematics, 1975, 22(1):52–56.

[6] Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji, NP-completeness of the Hamiltonian cycle problem for bipartite graphs, Journal of Information Processing, 1980, 3 (2): 73–76.

[7] Holton, D. A.; Manvel, B.; McKay, B. D., Hamiltonian cycles in cubic 3-connected bipartite planar graphs, Journal of Combi-natorial Theory, Series B, 1985, 38 (3): 279–297.

[8] Kelmans, A. K., Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles, American Mathematical Society Translations, 1994, 158 (2): 127–140.

[9] Aldred, R. E. L.; Bau, S.; Holton, D. A.; McKay, Brendan D., Nonhamiltonian 3-connected cubic planar graphs, SIAM Journal on Discrete Mathematics, 2000, 13 (1): 25–32.

[10] Hertel A. A survey & strengthening of BarneGe’s conjecture, University of Toronto, 2005.

[11] Feder, Tomas; Subi, Carlos, On BarneGe’s conjecture, ECCC, 2006.

[12] Florek, Jan, On BarneGe’s conjecture, Discrete Mathematics, 2010, 310 (10–11): 1531–1535.

[13] Alt, Helmut; Payne, Michael S.; Schmidt, Jens M.; Wood, David R., Thoughts on BarneGe’s conjecture, Australasian Journal of Combinatorics, 2016, 64 (2): 354–365.

[14] Kardoˇs, F., Acomputer-assisted proof of the BarneGe-Goodey Conjecture: not only fullerene graphs are hamiltonian, SIAM Journal on Discrete Mathematics, 2020, 34 (1): 62–100.

[15] P. J. Heawood. On the four-colour map theorem, Quart. J. Pure Appl. Math., 1898, 29: 270–285.

[16] Bagheri Gh B, Feder T, Fleischner H, et al. Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture [J]. Journal of Graph Theory, 2021, 96(2): 269-288.

[17] Florek J. Graphs with multi-$4 $-cycles and the Barnette's conjecture [J]. arXiv preprint arXiv:2002.05288, 2020.

[18] Gorsky M, Steiner R, Wiederrecht S. Matching theory and Barnette's conjecture [J]. Discrete Mathematics, 2023, 346(2): 113249.

[19] Gh B B, Feder T, Fleischner H, et al. On finding hamiltonian cycles in Barnette graphs [J]. Fundamenta Informaticae, 2022, 188.

[20] Bej S. Hamiltonian cycles in annular decomposable Barnette graphs [J]. Journal of Discrete Mathematical Sciences and Cryptography, 2022: 1-15.

Full-Text HTML

A Note on Barnette’s Conjecture

How to cite this paper: Zijun Xiao. (2023) A Note on Barnette’s Conjecture. Journal of Applied Mathematics and Computation, 7(2), 304-311.

DOI: http://dx.doi.org/10.26855/jamc.2023.06.012