Cubic bipartite non-hamiltonian graphs

Home CAAGT Authors Gunnar Brinkmann Jan Goedgebeur Brendan McKay

Cubic bipartite non-hamiltonian graphs 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 the following article we show that there is no smaller counterexample: G. Brinkmann, J. Goedgebeur and B.D. McKay, The Minimality of the Georges-Kelmans Graph, 17 pages, 2021. Preprint: (arXiv). This webpage contains the source code of the programs we used in our proof that there is no smaller non-hamiltonian 3-connected bipartite cubic graph than the Georges-Kelmans graph (which has 50 vertices). Notes: Most of these programs were written specifically to prove the above result and are not intended to be used or adjusted to generate other kinds of graphs. The independent implementations are not optimised as they were only written to independently verify the results of the main programs up to reasonable orders. When we refer to certain Lemmas, Theorems or Figures in the description of the programs, the labels correspond to the labelling used in the arXiv-manuscript. Programs: minibaum: Generator for cubic graps which we used to generate bipartite cubic graphs. genreg: Generator for regular graphs designed by Markus Meringer which Gunnar Brinkmann extended so it can also generate bipartite graphs efficiently. To use this extension, combine genreg_plus_bip.c and gendef.h with the original source files of genreg. cubhamg: Program which is part of the nauty package and which was used to search for hamiltonian cycles containing or avoiding certain edges. multi_hamiltonian-forbidden-edge.c: Program which tests if a given graph contains a forbidden edge (as defined in the proof of Lemma 2.2). The same test was also independently done using the program cubhamg which is part of the nauty package. multi_hamiltonian-forced-edge.c: Program which tests if a given graph contains a forced edge (as defined in the proof of Lemma 2.2). The same test was also also independently done using the program cubhamg which is part of the nauty package. test_type1_edge.c: Program which tests if a given graph contains a type 1 edge (as defined in the proof of Lemma 2.3). The same test was also independently done using the program cubhamg which is part of the nauty package. test_type2_edge.c: Program which tests if a given graph contains a type 2 edge (as defined in the proof of Lemma 2.3). The same test was also independently done using the program cubhamg which is part of the nauty package. multigraph.c: Program which was used to generate 5-pieces as defined in the proof of Lemma 2.4. make5pieces.c: Independent algorithm which was used in combination with minibaum to generate 5-pieces, thereby verifying the results of multigraph.c for 5-pieces up to 29 vertices. determine_class_of_5pieces.c: Program to determine the class of a 5-piece (cf. Lemma 2.4). minibaum-irred-8cycle.c: Modified version of minibaum which was adjusted to generate all irreducible bipartite cubic graphs of girth 6 (i.e. graphs which do not have an 8-cycle reduction from Figure 7) and which was used for part (a) of the proof of Theorem 1.1. is_reducible_tutte.c: Independently written filter to test if a given graph is irreducible. This filter was used in combination with the original version of minibaum to independently verify the results obtained by minibaum-irred-8cycle.c up to 40 vertices. xcubhamg6.c: Program which was used in combination with minibaum to generate all connected bipartite cubic graphs with at most 40 vertices that may be the reduction of a bipartite cubic graph of girth 6 (cf. part (b) of the proof of Theorem 1.1). 4tuples_are_extentable.c: Independently written filter to test if a given graph may be the reduction of a bipartite cubic graph of girth 6. This was used to independently verify the results obtained by xcubhamg6.c up to 34 vertices. plantri: Program which can be used to generate various types of planar graphs. This was used to generate 3-connected planar bipartite cubic graphs (cf. Theorem 4.1). multi_genus.c: Program which computes the genus of a graph. Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.