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

Stephan Brandt, Hajo Broersma, Reinhard Diestel, Matthias Kriesell

Research output: Book/ReportReportProfessional

8 Downloads (Pure)


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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages21
Publication statusPublished - 2002

Publication series

NameHamburger Beiträge zur Mathematik
PublisherUniversity of Hamburg

Fingerprint Dive into the research topics of 'Global connectivity and expansion: long cycles and factors in <i>f</i>-connected graphs'. Together they form a unique fingerprint.

Cite this