JAMC
A Note on Barnette’s Conjecture
TOTAL VIEWS: 2528
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.
How to cite this paper
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
More Articles
- Application of Association Rule Mining in Supermarket Sales Strategies
- Research on the Balanced Development of Primary Education in Shaanxi Province
- On the Infiltration of Mathematical Culture in Middle School Mathematics Teaching
- Analysis of Time Series Data via Quasi-Least Squares Technique
- A New Grey Prediction IANGM (1,1, k, k2) Model
- Joint Moments of Surplus Immediately Before Ruin and Deficit at Ruin in the Renewal Risk Model