On minimally highly vertex-redundantly rigid graphs

Viktória Kaszanitzky, Csaba Király


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-08}

Last modification: 13.3.2018. Please email your comments to Tamás Király!