On the Edge-Expansion of Graphs
- 1 June 1997
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 6 (2) , 145-152
- https://doi.org/10.1017/s096354839700299x
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=[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.Keywords
This publication has 0 references indexed in Scilit: