On the Edge-Expansion of Graphs

Research output: Contribution to journalArticlepeer-review

40 Scopus citations


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
Issue number2
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


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

Cite this