The minimality of the Georges–Kelmans graph

Brinkmann, Gunnar; Goedgebeur, Jan; McKay, Brendan

doi:10.1090/mcom/3701

The minimality of the Georges–Kelmans graph
HTML articles powered by AMS MathViewer

by Gunnar Brinkmann, Jan Goedgebeur and Brendan D. McKay;

Math. Comp. 91 (2022), 1483-1500

DOI: https://doi.org/10.1090/mcom/3701

Published electronically: November 17, 2021

HTML | PDF

Abstract:

In 1971, Tutte wrote in an article that it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian. Motivated by this remark, Horton constructed a counterexample on $96$ vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts—even if they have girth 6—it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs.

In 1969 Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnette’s conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.

References

R. E. L. Aldred, G. Brinkmann, and B. D. McKay, Announcement about Barnette’s conjecture, 2000, https://www.fmf.uni-lj.si/~mohar/Problems/P4BarnetteConjecture.html.
D. Barnette, Conjecture 5. Recent progress in combinatorics, Proceedings of the Third Waterloo Conference on Combinatorics, Academic Press, New York, 1969.
J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 411988, DOI 10.1007/978-1-349-03521-2
Gunnar Brinkmann, Fast generation of cubic graphs, J. Graph Theory 23 (1996), no. 2, 139–149. MR 1408342, DOI 10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.3.CO;2-1
G. Brinkmann, A practical algorithm for the computation of the genus, preprint arXiv:2005.08243, 2020.
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, and Hadrien Mélot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (2013), no. 1-2, 311–314. MR 2973372, DOI 10.1016/j.dam.2012.07.018
G. Brinkmann, J. Goedgebeur, and B. D. McKay, Software archive for cubic bipartite non-hamiltonian graphs, 2021, https://caagt.ugent.be/cubic-bip-nonham.
Gunnar Brinkmann and Brendan D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), no. 2, 323–357. MR 2357364
Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
M. N. Ellingham, Cycles in 3-connected cubic graphs, Master’s thesis, University of Melbourne, 1982.
M. N. Ellingham and J. D. Horton, Non-Hamiltonian $3$-connected cubic bipartite graphs, J. Combin. Theory Ser. B 34 (1983), no. 3, 350–353. MR 714456, DOI 10.1016/0095-8956(83)90046-1
John P. Georges, Non-Hamiltonian bicubic graphs, J. Combin. Theory Ser. B 46 (1989), no. 1, 121–124. MR 982860, DOI 10.1016/0095-8956(89)90012-9
Roland Grund, Konstruktion schlichter Graphen mit gegebener Gradpartition, Bayreuth. Math. Schr. 44 (1993), 73–104 (German, with German summary). MR 1224774
D. A. Holton, B. Manvel, and B. D. McKay, Hamiltonian cycles in cubic $3$-connected bipartite planar graphs, J. Combin. Theory Ser. B 38 (1985), no. 3, 279–297. MR 796604, DOI 10.1016/0095-8956(85)90072-3
D. A. Holton and B. D. McKay, The smallest non-Hamiltonian $3$-connected cubic planar graphs have $38$ vertices, J. Combin. Theory Ser. B 45 (1988), no. 3, 305–319. MR 969251, DOI 10.1016/0095-8956(88)90075-5
J. D. Horton, On two-factors of bipartite regular graphs, Discrete Math. 41 (1982), no. 1, 35–41. MR 676860, DOI 10.1016/0012-365X(82)90079-6
A. K. Kelmans, Cubic bipartite cyclically $4$-connected graphs with no Hamiltonian cycles, Uspekhi Mat. Nauk 43 (1988), no. 3(261), 181–182 (Russian); English transl., Russian Math. Surveys 43 (1988), no. 3, 205–206. MR 955785, DOI 10.1070/RM1988v043n03ABEH001738
A. K. Kelmans, A. K. Kelmans, and A. K. Kelmans (eds.), Selected topics in discrete mathematics, American Mathematical Society Translations, Series 2, vol. 158, American Mathematical Society, Providence, RI, 1994. Translated from the Russian by A. D. Vaĭnshteĭn; Translation edited by Simeon Ivanov. MR 1269122, DOI 10.1090/trans2/158
Kolja Knauer and Petru Valicov, Cuts in matchings of 3-connected cubic graphs, European J. Combin. 76 (2019), 27–36. MR 3886509, DOI 10.1016/j.ejc.2018.09.004
William McCuaig, Edge reductions in cyclically $k$-connected cubic graphs, J. Combin. Theory Ser. B 56 (1992), no. 1, 16–44. MR 1182455, DOI 10.1016/0095-8956(92)90004-H
B. D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112, The latest version of the software is available at http://users.cecs.anu.edu.au/~bdm/nauty/.
Markus Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999), no. 2, 137–146. MR 1665972, DOI 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G
W. T. Tutte, On Hamiltonian circuits, J. London Math. Soc. 21 (1946), 98–101. MR 19300, DOI 10.1112/jlms/s1-21.2.98
W. T. Tutte, On the $2$-factors of bicubic graphs, Discrete Math. 1 (1971/72), no. 2, 203–208. MR 291010, DOI 10.1016/0012-365X(71)90027-6
N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298. MR 1725006