####

#### 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)