Global connectivity and expansion: long cycles and factors in f-connected graphs

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)