Degree-sum conjecture for graph rigidity

About 1 year old · traced to

For a graph GG, define

η(G)=min⁡uv∉E(G)(deg⁡G(u)+deg⁡G(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,d∈Nn,d\in\mathbb{N} and n>2d+2n>2d+2, then

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

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

References

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.