On minimally highly vertex-redundantly rigid graphs (Q5964987)

The paper studies \([k, d]\)-rigid graphs. A \([k,d]\)-rigid graph is said to be minimally \([k,d]\)-rigid if the omission of an arbitrary edge results in a graph that is not \([k,d]\)-rigid. It is known that an \(n\)-vertex \([2,2]\)-rigid graph has at least \(2n-1\) edges and this bound is sharp. The present paper extends this lower bound for arbitrary values of \(k\) and \(d\) and shows its sharpness for the cases, where \(k=2\) and \(d\) is arbitrary and where \(k=d=3\). It also gives a sharp upper bound for the number of edges of minimally \([k,d]\)-rigid graphs for all \(k\).