TOPICS
Search

Ramanujan Graph


A Ramanujan graph is a connected d-regular graph whose adjacency eigenvalues other than d and -d have absolute value at most 2sqrt(d-1). The eigenvalue -d occurs for connected bipartite regular graphs and is excluded as a trivial eigenvalue. For a nonbipartite graph only d is excluded.

Signing the edges of a regular graph to control both extremes of its signed adjacency matrix spectrum is the Bilu-Linial signing conjecture. Xu (2026) reported a deterministic polynomial-time signing algorithm establishing its bipartite case.


See also

Adjacency Matrix, Bilu-Linial Signing Conjecture, Bipartite Graph, Graph Spectrum, Regular Graph

Explore with Wolfram|Alpha

References

Xu, Z. "A Deterministic Algorithm for Signing Bipartite Graphs at the Ramanujan Bound." 7 Oct 2026. https://arxiv.org/abs/2610.09972.

Cite this as:

Weisstein, Eric W. "Ramanujan Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RamanujanGraph.html

Subject classifications