Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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

by Gunnar Brinkmann, Jan Goedgebeur and Brendan D. McKay HTML | PDF
Math. Comp. 91 (2022), 1483-1500


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.

Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2020): 05C45, 05C85, 05C10
  • Retrieve articles in all journals with MSC (2020): 05C45, 05C85, 05C10
Additional Information
  • Gunnar Brinkmann
  • Affiliation: Department of Applied Mathematics, Computer Science & Statistics, Ghent University, 9000 Ghent, Belgium
  • MR Author ID: 252206
  • Email:
  • Jan Goedgebeur
  • Affiliation: Department of Computer Science, KU Leuven Campus Kulak, 8500 Kortrijk, Belgium; Department of Applied Mathematics, Computer Science and Statistics, Ghent University, 9000 Ghent, Belgium; and Computer Science Department, University of Mons, 7000 Mons, Belgium
  • MR Author ID: 945364
  • ORCID: 0000-0001-8984-2463
  • Email:
  • Brendan D. McKay
  • Affiliation: Department of Computing, Australian National University, Canberra Australian Capitol Territory 2601, Australia
  • MR Author ID: 122480
  • Email:
  • Received by editor(s): March 17, 2021
  • Received by editor(s) in revised form: August 31, 2021
  • Published electronically: November 17, 2021
  • Additional Notes: The second author was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO). The third author was supported by a Francqui International Professorship.
  • © Copyright 2021 by the authors
  • Journal: Math. Comp. 91 (2022), 1483-1500
  • MSC (2020): Primary 05C45, 05C85, 05C10
  • DOI:
  • MathSciNet review: 4405503