TOPICS
Search

Laplacian S_n,n Conjecture

The Laplacian S_(n,n) conjecture (Fallat et al. 2005) asserted that no simple graph on n>=2 vertices has a Laplacian matrix whose graph spectrum is

S_(n,n)={0,1,...,n-1}.

Fallat et al. (2005) proved the conjecture for n<=11, for prime n, and for n congruent to 2 or 3 modulo 4. Goldberger and Neumann (2013) proved it for n>=6649688933, and Johnston et al. (2026) proved the case n=12. Together, these results established the conjecture for 2<=n<=15 and n>=6649688933.

Johnston (2026) reported a proof of all remaining cases. The cases n<=31 are handled by roughly 10,000 exact linear programming infeasibility certificates. For n>=32, inequalities satisfied by any possible counterexample are combined with exact certificates expressing certain polynomials as sums of squares. The author reports substantial assistance from ChatGPT-5.5, GPT-5.6 Sol, and GPT-6 Astra. GPT-6 Astra originally wrote the accompanying verification code, while the author checked the proofs and computations. As of Sep. 27, 2026, independent specialist review had not been reported.

See also

Graph Spectrum, Laplacian Matrix

Explore with Wolfram|Alpha

References

Fallat, S. M.; Kirkland, S. J.; Molitierno, J. J.; and Neumann, M. "On Graphs Whose Laplacian Matrices Have Distinct Integer Eigenvalues." J. Graph Theory 50, 162-174, 2005. https://doi.org/10.1002/jgt.20102.Goldberger, A. and Neumann, M. "On a Conjecture on a Laplacian Matrix with Distinct Integral Spectrum." J. Graph Theory 72, 178-208, 2013.Johnston, N. "The Laplacian S_(n,n) Conjecture Is True." 22 Sep 2026. https://arxiv.org/abs/2609.26895.Johnston, N.; Plosker, S.; and Vaillancourt, S. "Laplacian Integral Graphs with Distinct Eigenvalues." Linear Algebra Appl. 720, 262-281, 2026.

Cite this as:

Weisstein, Eric W. "Laplacian S_n,n Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LaplacianSnnConjecture.html

Subject classifications