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. ISSN 0209-9683

PDF
Restricted to UT campus only: Request a copy
287Kb

Abstract:	Given a function $f: {\mathbb N}\to{\mathbb R}$ , call an $n$ -vertex graph $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.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/63673
Official URL:	http://dx.doi.org/10.1007/s00493-006-0002-5
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 237594