Skip to main content

Research Repository

Advanced Search

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

Brandt, S.; Broersma, H.J.; Diestel, R.; Kriesell, M.

Authors

S. Brandt

H.J. Broersma

R. Diestel

M. Kriesell



Abstract

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.

Citation

Brandt, S., Broersma, H., Diestel, R., & Kriesell, M. (2006). Global connectivity and expansion : long cycles and factors in f-connected graphs. Combinatorica, 26(1), 17-36. https://doi.org/10.1007/s00493-006-0002-5

Journal Article Type Article
Publication Date 2006
Deposit Date Jan 12, 2007
Journal Combinatorica
Print ISSN 0209-9683
Electronic ISSN 1439-6912
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 26
Issue 1
Pages 17-36
DOI https://doi.org/10.1007/s00493-006-0002-5
Keywords Global connectivity, Factor, Long cycle, Hamiltonian cycle.

You might also like



Downloadable Citations