Extremal families of redundantly rigid graphs in three dimensions.

A rigid graph G is said to be k -vertex (resp. k -edge) rigid in R d if it remains rigid after the removal of less than k vertices (resp. edges). The definition of k -vertex (resp. k -edge) globally rigid graphs in R d is similar. We study each of these four versions of redundant (global) rigidity and determine the smallest number of edges in a k -vertex (resp. k -edge) rigid (resp. globally rigid) graph on n vertices in R 3 for all positive integers k , except for four special cases, where we provide a close-to-tight bound. [ABSTRACT FROM AUTHOR]