A Ramanujan graph is a connected -regular graph whose adjacency
eigenvalues other than
and
have absolute value at most
. The eigenvalue
occurs for connected bipartite regular graphs and is excluded as a trivial eigenvalue.
For a nonbipartite graph only
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.