Merris's anti-regular graph accessibility conjecture

Let EnE_n be the degree anti-regular graph, meaning the unique connected graph whose vertex degrees attain every value from 11 through n1n-1. Let ω(En)\omega(E_n) denote its minimum relative forest accessibility. Merris's conjecture.

ω(En)=12(n+1).\omega(E_n)=\frac{1}{2(n+1)}.

This conjecture identifies the minimum relative forest accessibility of the degree anti-regular graph. The supplied source evidence reports that it was disproved by a counterexample 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

2 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.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.