Algebraic connectivity bound for complete multipartite graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.