Indexed metadata
On the Edge-Expansion of Graphs
NOGA ALON
Source record
Source: Crossref
Published: Jun 1, 1997
DOI: 10.1017/s096354839700299x
Open original source ↗Source abstract
It is shown that if n > n 0 ( 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 .
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.