The stronger edge bound conjecture for stress-independent graphs

Let G=(V,E)G=(V,E) be a dd-stress-independent graph, where dd-stress independence is the stress condition defined in the paper. Assume that GG has sufficiently many vertices.

Stronger edge bound conjecture. The number of edges satisfies

E(d+1)V(d+1)2.|E|\leq (d+1)|V|-(d+1)^2.

The theorem immediately preceding this conjecture gives the weaker bound (d+1)V(d+22)(d+1)|V|-\binom{d+2}{2} for suitable subgraphs. The conjecture proposes a stronger asymptotic upper bound, but does not specify the threshold for “sufficiently many” vertices.

Sources & referencesView supporting material

Primary source

Dániel Garamvölgyi, Bill Jackson and Tibor Jordán, “Sparsity, Stress-Independence and Globally Linked Pairs in Graph Rigidity Theory”, arXiv:2509.03150 (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.