Merris's algebraic-connectivity conjecture for graph accessibility

Let GG be a graph on nn vertices. Let a(G)a(G) denote its algebraic connectivity, and let ω(G)\omega(G) denote the minimum entry of its matrix of relative forest accessibilities. Merris's conjecture.

a(G)2(n+1)ω(G).a(G) \geq 2(n+1)\omega(G).

This conjecture relates algebraic connectivity to the smallest relative forest accessibility of a graph. It was disproved by a counterexample given in Zhang's work.

Sources & referencesView supporting material

Primary source

Enide Andrade and Geir Dahl, “Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs”, arXiv:2509.18773 (2025).

Additional references

3 papers in this index state this conjecture (2011–2025). The statement above is taken from the most recent of them; the others are arXiv:1111.2896, arXiv:1111.2897.

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.