We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

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.

Item Type:Article
Keywords:Global connectivity, Factor, Long cycle, Hamiltonian cycle.
Full text:Full text not available from this repository.
Publisher Web site:
Record Created:12 Jan 2007
Last Modified:08 Apr 2009 16:22

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Look up in GoogleScholar | Find in a UK Library