Abstract

Abstract A graph G is said to be k -vertex rigid in $$\mathbb {R}^d$$ R d if $$G-X$$ G - X is rigid in $$\mathbb {R}^d$$ R d for all subsets X of the vertex set of G with cardinality less than k . We determine the smallest number of edges in a k -vertex rigid graph on n vertices in $$\mathbb {R}^2$$ R 2 , for all $$k\ge 4$$ k ≥ 4 . We also consider k -edge-rigid graphs, defined by removing edges, as well as k -vertex globally rigid and k -edge globally rigid graphs in $$\mathbb {R}^d$$ R d . For $$d=2$$ d = 2 we determine the corresponding tight bounds for each of these versions, for all $$k\ge 3$$ k ≥ 3 . Our results complete the solutions of these extremal problems in the plane. The result on k -vertex rigidity verifies a conjecture of Kaszanitzky and Király (Graphs Combin, 32:225–240, 2016). We also determine the degree of vertex redundancy of powers of cycles, with respect to rigidity in the plane, answering a question of Yu and Anderson (Int J Robust Nonlinear Control, 19(13):1427–1446, 2009).