No CrossRef data available.
Article contents
On the Edge-Expansion of Graphs
Published online by Cambridge University Press: 01 June 1997
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
It is shown that if n>n0(d) then any d-regular graph G=(V, E) on n vertices contains a set of u=[lfloor]n/2[rfloor] 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.
Information
- Type
- Research Article
- Information
- Copyright
- 1997 Cambridge University Press
You have
Access
- 37
- Cited by