  In this paper we study some open questions related to the smallest order
$f({\cal C},\lnot {\cal H})$ of a 4-regular graph which has a connectivity
property ${{\cal C}}$ but does not have a hamiltonian property ${\cal H}$. In
particular, ${\cal C}$ is either connectivity, 2-connectivity or 1-toughness
and ${\cal 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({\cal C},\lnot {\cal H})$ for all the pairs of
considered properties with the exception of ${\cal C}=$1-toughness, ${{\cal
H}}=$traceability. Even in this last case, we have nonetheless significantly
reduced the interval $[LB, UB]$ in which $f({\cal C},\lnot {\cal H})$ was known
to lie. Finally, we have shown that for each $n \geq f({\cal C},\lnot {\cal
H})$ ($n \geq UB$ in the last case) there exists a 4-regular graph on $n$
vertices which has property ${\cal C}$ but not property ${\cal H}$.
