Encyclopedia > Expander

  Article Content

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Monty Woolley

... of a broken leg in 1942's The Man Who Came to Dinner[?], which he had performed onstage before taking it to Hollywood. Academy Awards and Nominations 1945 - ...

 
 
 
This page was created in 47.4 ms