@article{ac0f73c1f2974b2287e34cbbe6217a88,
title = "Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs",
abstract = "Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(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)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)2. We conjecture that linear growth of f suffices to imply hamiltonicity.",
keywords = "MSC-05C70, MSC-05C38, MSC-05C40, MSC-05C45",
author = "Stephan Brandt and Hajo Broersma and Reinhard Diestel and Matthias Kriesell",
year = "2006",
month = feb,
doi = "10.1007/s00493-006-0002-5",
language = "English",
volume = "26",
pages = "17--36",
journal = "Combinatorica",
issn = "0209-9683",
publisher = "Janos Bolyai Mathematical Society",
number = "1",
}