Haemers's Laplacian eigenvalue conjecture for graph toughness

At least 4 years old · documented by

Let GG be a simple graph with minimum degree δ\delta. Let μ2\mu_2 and μn\mu_n denote the second-smallest and largest eigenvalues of the Laplacian matrix of GG, respectively, and let t(G)t(G) be its toughness. Haemers's conjecture.

t(G)≥μ2μn−δ.t(G)\geq\frac{\mu_2}{\mu_n-\delta}.

The source attributes this conjecture to Haemers and presents it as a proposed lower bound for the toughness of arbitrary graphs in terms of Laplacian eigenvalues. The supplied material does not state whether it has been resolved.

References

Primary source

Xiaofeng Gu and Willem H. Haemers, “Graph toughness from Laplacian eigenvalues”, arXiv:2104.03845 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.