Extremality conjecture for generalized path graphs

About 13 years old · traced to

Let d≥1d\geq 1 and let Pn,dP_{n,d} be the generalized path graph, an nn-vertex minimally dd-rigid graph. For a graph GG, let ad(G)a_d(G) denote its dd-dimensional algebraic connectivity. Extremality conjecture for generalized path graphs. If GG is a dd-rigid graph on nn vertices, then

ad(G)≥ad(Pn,d).a_d(G)\geq a_d(P_{n,d}).

The generalized path graphs satisfy ad(Pn,d)=Θd(1/n2)a_d(P_{n,d})=\Theta_d(1/n^2), so the conjecture proposes that they minimize dd-dimensional algebraic connectivity among nn-vertex dd-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

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.