Algebraic connectivity bound for complete multipartite graphs

From papers

Let d1d\geq 1 and k2k\geq 2. For positive integers n1,,nkn_1,\ldots,n_k, write n=n1++nkn=n_1+\cdots+n_k, and let Kn1,,nkK_{n_1,\ldots,n_k} be the complete kk-partite graph whose sides have sizes n1,,nkn_1,\ldots,n_k. The quantity ad(G)a_d(G) denotes the dd-dimensional algebraic connectivity of a graph GG. The complete multipartite connectivity conjecture. There exist constants cd,k,Md,k>0c_{d,k},M_{d,k}>0 such that, for all n1,,nkMd,kn_1,\ldots,n_k\geq M_{d,k},

ad(Kn1,n2,,nk)cd,kminnn1,nn2,,nnk.a_d(K_{n_1,n_2,\ldots,n_k})\geq c_{d,k}\cdot\min\\{n-n_1,n-n_2,\ldots,n-n_k\\}.

For d=1d=1 this is an equality, while for d2d\geq 2 the corresponding rigidity and exact-value questions remain open, particularly for complete multipartite graphs with at least three parts.

Progress summary

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

Sources & referencesView supporting material

Primary source

Yunseong Jung and Alan Lew, “Stiffness matrices of graph blow-ups and the d-dimensional algebraic connectivity of complete bipartite graphs”, arXiv:2504.01181 (2025).

Additional references

8 papers in this index state this conjecture (2009–2025). The statement above is taken from the most recent of them; the others are arXiv:2410.20189, arXiv:2309.09041, arXiv:2209.01030, arXiv:2207.12336, arXiv:2201.04225, arXiv:2012.00808, arXiv:0910.4774.

Solutions 0

No solutions have been posted yet.