Auchiche–Hansen's proximity and distance eigenvalue conjecture

At least 4 years old · documented by

Let GG be a connected graph on n≥4n\geq 4 vertices with diameter DD, proximity π\pi and distance spectrum ∂1≥…≥∂n\partial_1\geq \ldots \geq \partial_n. Auchiche–Hansen's conjecture.

π+∂\originalleft⌊2D3\aftergroup\originalright⌋>0.\pi + \partial_{\mathopen{}\mathclose\bgroup\originalleft\lfloor \frac{2D}{3} \aftergroup\egroup\originalright\rfloor} > 0.

This conjecture would strengthen a result of Merris on proximity and distance eigenvalues. It is refuted by a connected graph obtained from a path on 13 vertices by attaching sufficiently many pendant vertices; specifically, the construction gives a counterexample for all n≥190n\geq 190 pendant vertices.

References

Primary source

Adam Zsolt Wagner, “Constructions in combinatorics via neural networks”, arXiv:2104.14516 (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.