The asymptotically optimal algebraic-connectivity bound for bounded-degree trees

Let TT be a tree with nn vertices and maximum degree dd. The asymptotically optimal tree bound conjecture. As nn\rightarrow\infty for fixed dd,

λ2(T)d(d2)d11n+O(lnnn2).\lambda_{2}(T)\leq\frac{d(d-2)}{d-1}\frac{1}{n}+O\left(\frac{\ln n}{n^{2}}\right).

Here λ2(T)\lambda_{2}(T) denotes the algebraic connectivity of TT. The conjecture improves the paper's preceding general bound and is known in the source for the well-balanced Bethe trees; its validity for all trees with maximum degree dd remains open.

Sources & referencesView supporting material

Primary source

Theodore Kolokolnikov, “Maximizing algebraic connectivity for certain families of graphs”, arXiv:1412.6147 (2014).

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.