Construction of Barnette graphs whose large subgraphs are non-Hamiltonian

S. Pirzada; Mushtaq A. Shah

doi:10.2478/ausm-2019-0026

Abstract

Barnette’s conjecture states that every three connected cubic bipartite planar graph (CPB3C) is Hamiltonian. In this paper we show the existence of a family of CPB3C Hamiltonian graphs in which large and large subgraphs are non-Hamiltonian.

References

[1] T. Akiyama, T. Nishizeki and N. Saiton, NP-compleateness of the Hamiltonian cycle problem for bipartite graphs, Journal Information Processing, 3 (2) (1980), 73–76.
Search in Google Scholar Back to article
[2] R. Aldred, G. Brinkmann and B. D. McKay, Announcement, March 2000.
Search in Google Scholar Back to article
[3] D. Barnette, Conjecture 5, In W. T. Tutte ed. Recent Progress in Combinatorics, page 343 Academic press, New York, 1969.
Search in Google Scholar Back to article
[4] I. Cahit, Algorithmic proof of Barnette’s Conjecture, https://arxiv.org/pdf/0904.3431.pdf (2009).
Search in Google Scholar Back to article
[5] T. Feder and C. Subi, On Barnette’s Conjecture, Published on internet http://theory.stanford.edu/tomas/bar.ps.
Search in Google Scholar Back to article
[6] T. Fowler, Reducible Configurations for the Barnett’s conjecture, Unpublished manuscript August 2001.
Search in Google Scholar Back to article
[7] P. R. Goodey, Hamiltonian circuit in Polytopes with even sided faces, Israel J. Mathematics, 22 (1975) 52–56.
Search in Google Scholar Back to article
[8] B. Grunbaum, Polytopes, Graphs and Complexes, Bull. Amer. Math. Soc., 76 (1970) 1131–1201.
Search in Google Scholar Back to article
[9] J. Harant, A Note on Barnette’s Conjecture, Discussiones Mathematicae Graph Theory, 33 (2013) 133–137.
Search in Google Scholar Back to article
[10] A. Hertel, Hamiltonian Cycle in Sparse Graphs, Master’s thesis, University of Toronto, 2004.
Search in Google Scholar Back to article
[11] A. Hertel, A survey and strengthening of Barnette’s Conjecture, Department of Computer Science, University of Toronto, 2005.
Search in Google Scholar Back to article
[12] T. R. Jensen and B. Toft, Graph Coloring Problem, J. Wiley and Sons New York, 1995.10.1002/9781118032497
Search in Google Scholar Back to article
[13] A. K. Kalmans, Konstruktsii Kubicheskih Dvudolnyh 3-Svyaznyh Bez GamiltonovyhTsiklov, Sb.TrVNiii Sistem, issled., 10 (1986), 64–72.
Search in Google Scholar Back to article
[14] D. König,Über, Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77 (1916), 453–465.10.1007/BF01456961
Search in Google Scholar Back to article
[15] B. D. McKay, D. A. Holton and B. Manvel, Hamiltonian cycles in cubic 3- connected bipartite planar graphs, J. Combinatorial Theory, Series B, 38 (1985) 279–297.
Search in Google Scholar Back to article
[16] S. Pirzada, An Introduction to Graph Theory, Universities Press, Orient Blackswan, Hyderabad, 2012.
Search in Google Scholar Back to article
[17] C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory, 7 (1983), 169–176.10.1002/jgt.3190070205
Search in Google Scholar Back to article
[18] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956), 99–116.10.1090/S0002-9947-1956-0081471-8
Search in Google Scholar Back to article

Construction of Barnette graphs whose large subgraphs are non-Hamiltonian

Abstract

Paradigm

My account