Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Share/Save/Bookmark

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

[img]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:
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

 

Repository Staff Only: item control page

Metis ID: 237594