Expander
An expander graph is a graph with high vertex or edge expansion.
Let N(S) denote the set of neighbors of S (excluding S itself).
The Vertex Expansion of a graph is the minimum of |N(S)| / |S|.
Let E(A,B) denote the number of edges with one extremity in A and the other in B. Let /S denote the complement of S.
The Edge Expansion of a graph is the minimum E(S,/S) / |S|.
Referenced By
List of graph theory topics | List of mathematical topics (D-F) | List of mathematical topics (F-Z) | Pseudorandomness
|
