Degree-sum conjecture for graph rigidity

For a graph GG, define

η(G)=minuvE(G)(degG(u)+degG(v)),\eta(G)=\min_{uv\notin E(G)}\bigl(\deg_G(u)+\deg_G(v)\bigr),

and let g(n,d)g(n,d) be the smallest integer such that every nn-vertex graph GG with η(G)g(n,d)\eta(G)\geq g(n,d) is dd-rigid. Degree-sum conjecture. If n,dNn,d\in\mathbb{N} and n>2d+2n>2d+2, then

g(n,d)=n+d2.g(n,d)=n+d-2.

This is proposed after noting that the minimum-degree lower bound gives g(n,d)n+d2g(n,d)\geq n+d-2 in this regime; the paper does not state a resolution of the proposed equality.

Sources & referencesView supporting material

Primary source

Tibor Jordán, Xuemei Liu and Soma Villányi, “Degree Sum Conditions for Graph Rigidity”, arXiv:2510.25689 (2025).

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.