An ILP Approach to Determine Smallest 4-Regular Nonhamiltonian, Nontraceable, and Nonhomogeneously Taceable Graphs

Abstract: In this paper we study some open questions related to the smallest order (Formula presented.)-regular graph which has a connectivity property(Formula presented.) but does not have a hamiltonian property (Formula presented.). In particular, (Formula presented.) is either connectivity, (Formula presented.)-toughness and (Formula presented.) is hamiltonicity, homogeneous traceability or traceability. A standardtheoretical approach to these questions had already been used in the literature, but in many casesdid not succeed in determining the exact value of (Formula presented.). Here we have chosen to use Integer Linear Programming and to encode thegraphs that we are looking for as the binary solutions to a suitable set of linear inequalities. Thisway, there would exist a graph of order n with certain properties if and only if the corresponding ILP had a feasiblesolution, which we have determined through a branch-and-cut procedure. By using our approach,we have been able to compute (Formula presented.) for all the pairs of considered properties with the exception of (Formula presented.) traceability. Even in this last case, we have nonetheless significantly reducedthe interval (Formula presented.) in which (Formula presented.) was known to lie. Finally, we have shown that for each (Formula presented.) ((Formula presented.) in the last case) there exists a (Formula presented.)-regular graph on (Formula presented.) vertices which has property (Formula presented.) but not property (Formula presented.).