On the Edge-Expansion of Graphs

Research output: Contribution to journalArticle

33 Scopus citations

Abstract

It is shown that if n > n0(d) then any d-regular graph G = (V, E) on n vertices contains a set of u = ⌊n/2⌋ vertices which is joined by at most (d/2 - c√d)u edges to the rest of the graph, where c > 0 is some absolute constant. This is tight, up to the value of c.

Original languageEnglish (US)
Pages (from-to)145-152
Number of pages8
JournalCombinatorics Probability and Computing
Volume6
Issue number2
DOIs
StatePublished - Jan 1 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the Edge-Expansion of Graphs'. Together they form a unique fingerprint.

  • Cite this