Journal of Applied Mathematics and Computation

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

Date: July 31,2023 Hits: 336

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.

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

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

Copyright © 2020 Hill Publishing Group Inc.

All Rights Reserved.