Global connectivity and expansion: long cycles and factors in \(f\)-connected graphs (Q2495692): Difference between revisions

A graph \(G\) is called \(f\)-connected if every separation \((A,B)\) of \(G\) with \(| A\setminus B| \leq| B\setminus A| \) satisfies \(| A\cap B| \geq f(| A\setminus B| )\) where \(f:\mathbb{N}\setminus\{0\}\rightarrow\mathbb{R}\) is a (usually non-decreasing) function. The authors investigate relations between the \(f\)-connectedness of a graph and properties of its substructures. They prove 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)\geq 2k+1\), and contains a Hamilton cycle if \(f(k)\geq2(k+1)^2\). Their conjecture that linear growth of \(f\) suffices to imply Hamiltonicity is still open.