A graph $G=(V,E)$ is called $k$-rigid in $\R^d$ if $|V|\geq k+1$ and after deleting any set of at most $k-1$ vertices the resulting graph is rigid in $\R^d$. A $k$-rigid graph $G$ is called minimally $k$-rigid if the omission of an arbitrary edge results in a graph that is not $k$-rigid. B. Setvatius showed that a 2-rigid graph in $\R^2$ has at least $2|V|-1$ edges and this bound is sharp. We extend this lower bound for arbitrary values of $k$ and $d$ and show its sharpness for the cases where $k=2$ and $d$ is arbitrary and where $k=d=3$. We also provide a sharp upper bound for the number of edges of minimally $k$-rigid graphs in $\R^d$ for all $k$.

Bibtex entry:

@techreport{egres-14-08,

AUTHOR | = | {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba}, |

TITLE | = | {On minimally highly vertex-redundantly rigid graphs}, |

NOTE | = | {{\tt www.cs.elte.hu/egres}}, |

INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |

YEAR | = | {2014}, |

NUMBER | = | {TR-2014-08} |