On the Edge-Expansion of Graphs

Noga Alon

doi:10.1017/S096354839700299X

On the Edge-Expansion of Graphs

Noga Alon

Research output: Contribution to journal › Article › peer-review

43 Scopus citations

Abstract

It is shown that if n > n₀(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 language	English (US)
Pages (from-to)	145-152
Number of pages	8
Journal	Combinatorics Probability and Computing
Volume	6
Issue number	2
DOIs	https://doi.org/10.1017/S096354839700299X
State	Published - 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1017/S096354839700299X

Cite this

@article{048bf4d35d044aac8d79036080393894,

title = "On the Edge-Expansion of Graphs",

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.",

author = "Noga Alon",

year = "1997",

doi = "10.1017/S096354839700299X",

language = "English (US)",

volume = "6",

pages = "145--152",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "2",

}

TY - JOUR

T1 - On the Edge-Expansion of Graphs

AU - Alon, Noga

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0031521039&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031521039&partnerID=8YFLogxK

U2 - 10.1017/S096354839700299X

DO - 10.1017/S096354839700299X

M3 - Article

AN - SCOPUS:0031521039

SN - 0963-5483

VL - 6

SP - 145

EP - 152

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 2

ER -

On the Edge-Expansion of Graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this