|
Published in:
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:
| AUTHOR | = | {Kaszanitzky, Vikt{\'o}ria and Kir{\'a}ly, Csaba}, |
| TITLE | = | {On minimally highly vertex-redundantly rigid graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2014}, |
| NUMBER | = | {TR-2014-08} |