Hamiltonian cycles in annular decomposable Barnette graphs.

Bej, Saptarshi

doi:10.1080/09720529.2021.1961893

Open Access Research Article

Hamiltonian cycles in annular decomposable Barnette graphs.

^*Saptarshi BejCorresponding authorsaptarshibej24@gmail.com; saptarshi.bej@uni-rostock.deInstitute of Computer Science Ulmenstrasse 69 University of RostockRostock, 18057, GermanyView full profile →

* Corresponding author · click or hover a name for details

pp. 951–965Vol. 26Issue 4June 2023DOI: 10.1080/09720529.2021.1961893 Crossmark XML

Received:: 01 Jan 2021
Accepted:: 01 May 2021
Published Online:: 24 Feb 2022
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1416
Pages:: 951–965

Abstract

Barnette’s conjecture is an unsolved problem in graph theory. The problem states that every 3-regular (cubic), 3-connected, planar, bipartite (Barnette) graph is Hamiltonian. Partial results have been derived with restrictions on the number of vertices, several properties of face-partitions and dual graphs of Barnette graphs, while some studies focus just on structural characterizations of Barnette graphs. Noting that spider web graphs are a subclass of Annular Decomposable Barnette (ADB graphs) graphs and are Hamiltonian, we study ADB graphs and their annular-connected subclass (ADB-AC graphs). We show that ADB-AC graphs can be generated from the smallest Barnette graph (B0) using recursive edge operations. We derive several conditions assuring the existence of Hamiltonian cycles in ADB-AC graphs without imposing restrictions on the number of vertices, face size or any other constraints on the face partitions. We show that there can be two types of annuli in ADB-AC graphs, ring annuli and block annuli. Our main result is, ADB-AC graphs having non-singular sequences of ring annuli are Hamiltonian.

Keywords

Barnette conjecture Hamiltonian graphs Annular decomposition Planar cubic graphs Bipartite polyhedral graphs

Subject Classifications

05C1005C4005C45

References

[1] Behrooz Bagheri Gh, Tomas Feder, Herbert Fleischner, and Carlos Subi. Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of barnette’s conjecture. Journal of Graph Theory, pages 1-20, 2020.
[2] Jean-Claude Bermonf, Johny Bond, Carole Martin, Aleksandar Pekec, and Fred S. Roberts. Optimal orientations of annular networks. Journal of Interconnection Networks, 01(01) : 21-46, 2000.
[3] Jan Florek. On barnettes conjecture. Discrete Mathematics, 310(10) : 1531-1535, 2010.
[4] Jan Florek. On barnette’s conjecture and h+-h+- property. Electron. Notes Discret. Math., 43 : 375-377, 2013.
[5] Jan Florek. Remarks on barnettes conjecture. Journal of Combinatorial Optimization, 39(1) : 149-155, 2020.
[6] M. Hasheminezhad, S. Mehdi Hashemi, B. McKay, and M. Tahmasbi. Rectangular-radial drawings of cubic plane graphs. Computational Geometry, 43(9) : 767-780, 2010.
[7] D. A. Holton, B. Manvel, and B. D. McKay. Hamiltonian cycles in cubic 3-connected bipartite planar graphs. J. Combin. Theory Ser. B, 38(3) : 279-297, 1985.
[8] D.A Holton and B.D McKay. The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices. Journal of Combinatorial Theory, Series B, 45(3) : 305-319, 1988.
[9] J.D. Horton. On two-factors of bipartite regular graphs. Discrete Mathematics, 41(1) : 35-41, 1982.
[10] S. M. Hosamani, P. V. Patil, and S. H. Malghan. First zagreb coindex of hamiltonian graphs. Journal of Information and Optimization Sciences, 38(3-4) : 417-422, 2017.
[11] Shin-Shin Kao and Lih-Hsing Hsu. Spider web networks: a family of optimal, fault tolerant, hamiltonian bipartite graphs. Applied Mathematics and Computation, 160(1) : 269-282, 2005.
[12] Xiaoyun Lu. A note on barnettes conjecture. Discrete Mathematics, 311(23) : 2711-2715, 2011.
[13] Grace Misereh and Yuri Nikolayevsky. Annular and pants thrackles. Discret. Math. Theor. Comput. Sci., 20, 2018.
[14] P. Siva Kota Reddy and P. S. Hemavathi. Generalization of bipartite graphs. Journal of Discrete Mathematical Sciences and Cryptography, 23(3) : 787-793, 2020.
[15] W. T. Tutte. On Hamiltonian circuits. J. London Math. Soc., 21:98{101, 1946.

Views: 212Downloads: 9Citations: 0