Algebraic connectivity bound for complete multipartite graphs

At least 16 years old · documented by

Let d≥1d\geq 1 and k≥2k\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,…,nk≥Md,kn_1,\ldots,n_k\geq M_{d,k},

ad(Kn1,n2,…,nk)≥cd,k⋅min⁡n−n1,n−n2,…,n−nk.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 d≥2d\geq 2 the corresponding rigidity and exact-value questions remain open, particularly for complete multipartite graphs with at least three parts.

References

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.

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.