Given a function $f\colon\N\to\R$, call an $n$-vertex graph
\emph{$f$-connected} if separating off $k$ vertices requires the
deletion of at
least $f(k)$ vertices whenever $k\le (n-f(k))/2$. This is a common
generalization of vertex connectivity (when $f$ is constant) and
expansion
(when $f$ is linear). We show that an $f$-connected graph contains
a cycle of
length linear in~$n$ if $f$ is any linear function, contains a
1-factor and a
2-factor if $f(k)\ge 2k+1$, and contains a Hamilton cycle if $f(k)
\ge
2(k+1)^2$. We conjecture that linear growth of $f$ suffices to
imply
hamiltonicity.
Download (PDF)