Algebraic connectivity bound for complete multipartite graphs
Let and . For positive integers , write , and let be the complete -partite graph whose sides have sizes . The quantity denotes the -dimensional algebraic connectivity of a graph . The complete multipartite connectivity conjecture. There exist constants such that, for all ,
For this is an equality, while for 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
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.