Proving hamiltonian properties in connected 4-regular graphs: an ILP-based approach

In this paper we study some open questions related to the smallest order $f(\mathcal{C},\mathrm{\neg }\mathcal{H})$ of a 4-regular graph which has a connectivity property $\mathcal{C}$ but does not have a hamiltonian property $\mathcal{H}$. In particular, $\mathcal{C}$ is either connectivity, 2-connectivity or 1-toughness and $\mathcal{H}$ is hamiltonicity, homogeneously traceability or traceability. A standard theoretical approach to these questions had already been used in the literature, but did not succeed in determining the exact value of $f()$. Here we have chosen to use Integer Linear Programming and to encode the graphs that we are looking for as the binary solutions to a suitable set of linear inequalities. This way, there would exist a graph of order $n$ with certain properties if and only if the corresponding ILP had a feasible solution, which we have determined through a branch-and-cut procedure. By using our approach, we have been able to compute $f(\mathcal{C},\mathrm{\neg }\mathcal{H})$ for all the pairs of considered properties with the exception of $\mathcal{C}=$1-toughness, ${{\cal H}}=$traceability. Even in this last case, we have nonetheless significantly reduced the interval $[LB,UB]$ in which $f(\mathcal{C},\mathrm{\neg }\mathcal{H})$ was known to lie. Finally, we have shown that for each $n \geq f({\cal C},\lnot {\cal H})$($n \geq UB$inthelastcase)thereexistsa4-regulargraphon$n$verticeswhichhasproperty${\cal C}$butnotproperty${\cal H}$.