Published in:
Graphs and Combinatorics 32, 225–240 (2016). DOI link
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 egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2014}, |
NUMBER | = | {TR-2014-08} |