An expander graph belongs to a family of graphs of uniformly bounded maximum degree, with vertex
counts tending to infinity, whose edge expansion
constants are bounded below by a positive constant independent of the vertex
count. For a family of -regular graphs, a two-sided
spectral expansion condition is
for every eigenvalue
of the normalized adjacency
matrix restricted to the subspace orthogonal to
the constant vector, with a fixed
(Kharlampovich and Vdovina 2026).
Expander Graph
See also
Adjacency Matrix, Edge Expansion Constant, Regular Graph, Spectral GapExplore with Wolfram|Alpha
References
Hoory, S.; Linial, N.; and Wigderson, A. "Expander Graphs and Their Applications." Bull. Amer. Math. Soc. 43, 439-561, 2006. https://doi.org/10.1090/S0273-0979-06-01126-8.Cite this as:
Weisstein, Eric W. "Expander Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ExpanderGraph.html