Extremality conjecture for generalized path graphs
Let and let be the generalized path graph, an -vertex minimally -rigid graph. For a graph , let denote its -dimensional algebraic connectivity. Extremality conjecture for generalized path graphs. If is a -rigid graph on vertices, then
The generalized path graphs satisfy , so the conjecture proposes that they minimize -dimensional algebraic connectivity among -vertex -rigid graphs. Its resolution is not given in the source.
References
Primary source
Alan Lew, Eran Nevo, Yuval Peled and Orit E. Raz, “Rigidity expander graphs”, arXiv:2304.01306 (2023).
Additional references
3 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:2003.00942, arXiv:1310.1386.
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.