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

Stephan Brandt, Hajo Broersma, Reinhard Diestel, Matthias Kriesell

Research output: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

Abstract

Given a function f : ℕ→ℝ, 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
Pages (from-to)17-36
Number of pages20
JournalCombinatorica
Volume26
Issue number1
DOIs
Publication statusPublished - Feb 2006

Keywords

  • MSC-05C70
  • MSC-05C38
  • MSC-05C40
  • MSC-05C45

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