RIGIDITY THEORY AND ITS APPLICATIONS

NEW

Problem: The quoted “Full characterization/ Examples ...” is ambiguous: a full classification in dimension $d\ge3$ would include the usual hard generic-rigidity problem. I formalize the “Examples” branch as follows.

Let $d\ge3$, $k\ge1$. A finite simple graph $G$ is $k$-vertex-rigid in $\mathbb R^d$ if $G-X$ is generically infinitesimally rigid in $\mathbb R^d$ for every $X\subseteq V(G)$ with $|X|\le k-1$. It is strongly minimal if no $k$-vertex-rigid graph on the same number of vertices has fewer edges.

Result: For every $d\ge3$ and $k\ge1$, both

are strongly minimal $k$-vertex-rigid graphs in $\mathbb R^d$. The second family is non-complete.

Proof. Let $C=\binom{d+1}{2}$. Any generically rigid graph on $N\ge d+1$ vertices has at least $dN-C$ edges, since its rigidity matrix must have rank $dN-C$.

Also, $K_N$ is rigid for $N\ge d+1$, and $K_N-e$ is rigid for $N\ge d+2$: start from a rigid $K_{d+1}$, obtain $K_{d+2}-e$ by a $0$-extension adding one vertex joined to $d$ old vertices, and then add remaining vertices similarly. A $0$-extension preserves generic rigidity because the new vertex is constrained by $d$ generically spanning edge directions.

For $K_{d+k}$: deleting at most $k-1$ vertices leaves a complete graph on at least $d+1$ vertices, hence rigid. Conversely, if $H$ is $k$-vertex-rigid on $d+k$ vertices, then every $(d+1)$-set $S$ is the complement of $k-1$ vertices, so $H[S]$ is rigid. It must therefore have at least $C$ edges, hence is complete. Every pair lies in some such $S$, so $H=K_{d+k}$.

For $K_{d+k+1}-e$: deleting at most $k-1$ vertices leaves $K_N$ or $K_N-e$ with $N\ge d+2$, hence rigid. Conversely, let $H$ be $k$-vertex-rigid on $d+k+1$ vertices. If $H$ had two nonedges, their endpoints fit inside some $(d+2)$-set $S$ because $d\ge3$. Then $H[S]$ would have at most

edges, but rigidity on $d+2$ vertices requires at least

edges, a contradiction. Thus $H$ has at most one nonedge, so

with equality attained by $K_{d+k+1}-e$. Hence it is strongly minimal.

Audit: the hypotheses $d\ge3$, $k\ge1$, finite simple graphs, and deletion of at most $k-1$ vertices were used exactly. The result supplies examples, not a full classification.

Citation: No full-characterization citation is used. The rigidity-matrix rank bound and $0$-extension preservation are standard; see L. Asimow and B. Roth, “The rigidity of graphs,” Trans. Amer. Math. Soc. 245 (1978), 279–289.