Brandt, S. and Broersma, H. J. and Diestel, R. and Kriesell, M. (2006) 'Global connectivity and expansion : long cycles and factors in f-connected graphs.', Combinatorica., 26 (1). pp. 17-36.
Given a function f : N → R, 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:||Global connectivity, Factor, Long cycle, Hamiltonian cycle.|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/s00493-006-0002-5|
|Record Created:||12 Jan 2007|
|Last Modified:||08 Apr 2009 16:22|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|