Applications of Integer Programming Methods to Cages

  • Frans J.C.T. de Ruiter
  • Norman L. Biggs
Keywords: Integer programming applications, Cage problem


The aim of this paper is to construct new small regular graphs with girth $7$ using integer programming techniques. Over the last two decades solvers for integer programs have become more and more powerful and have proven to be a useful aid for many hard combinatorial problems. Despite successes in many related fields, these optimisation tools have so far been absent in the quest for small regular graphs with a given girth. Here we illustrate the power of these solvers as an aid to construct small regular girth $7$ graphs from girth $8$ cages.

Article Number