|
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.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Poston, Christopher and Roach, Ryan}, |
| TITLE | = | {Extremal families of redundantly rigid graphs in three dimensions}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-22} |