TR-2014-08

On minimally highly vertex-redundantly rigid graphs

Viktória Kaszanitzky, Csaba Király

Published in:
Graphs and Combinatorics 32, 225–240 (2016). DOI link



Abstract

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}
}


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