Finding Uniquely Hamiltonian Graphs of Minimum Degree Three with Small Crossing Numbers

Abstract

In graph theory, a prominent conjecture of Bondy and Jackson states that every uniquely hamiltonian planar graph must have a vertex of degree two. In this work we try to find uniquely hamiltonian graphs with minimum degree three and a small crossing number by minimizing the number of crossings in an embedding and the number of degree-two vertices. We formalize an optimization problem for this purpose and propose a general variable neighborhood search (GVNS) for solving it heuristically. The several different types of used neighborhoods also include an exponentially large neighborhood that is effectively searched by means of branch and bound. To check feasibility of neighbors we need to solve hamiltonian cycle problems, which is done in a delayed manner to minimize the computation effort. We compare three different configurations of the GVNS. Although our implementation could not find a uniquely hamiltonian planar graph with minimum degree three disproving Bondy and Jackson´s conjecture, we were able to find uniquely hamiltonian graphs of minimum degree three with crossing number four for all number of vertices from 10 to 100.