|
A graph $G$ is said to be $k$-vertex rigid in $\R^d$ if $G-X$ is
rigid in $\R^d$ for all subsets $X$ of the vertex set of $G$ with
cardinality less than $k$.
We determine the smallest number of edges in
a $k$-vertex rigid graph on $n$ vertices in $\R^2$, for all $k\geq 4$.
We also consider
$k$-edge-rigid graphs, defined by removing edges, as well as $k$-vertex globally rigid and $k$-edge globally rigid graphs in $\R^d$.
For $d=2$ we determine the
corresponding tight bounds for each of these versions, for all $k\geq 3$.
Our results complete the solutions of these extremal problems in the plane.
The result on $k$-vertex rigidity verifies a conjecture of Kaszanitzky and Kir\'aly ({\it Graphs and Combinatorics}, 2016).
We also determine the degree of vertex redundancy of powers of cycles, with respect to rigidity in the plane,
answering a question of Yu and Anderson ({\it Int. J. Robust Nonlinear Control, 2009}).
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor}, |
| TITLE | = | {Minimum size highly redundantly rigid graphs in the plane}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-21} |