论文标题
最小的全球刚性图
Minimally globally rigid graphs
论文作者
论文摘要
图$ g =（v，e）$在$ \ mathbb {r}^d $中固定在全球范围内。在本文中，我们考虑了最小的全球刚性图，其中删除任意边缘会破坏全球刚度。我们证明，如果$ g =（v，e）$在至少$ d+2 $ vertices上的$ \ mathbb {r}^d $中的全球刚度最小，则是$ | e | e | \ leq（d+1）| v | - \ binom {d+2} {2} {2} {2} $。这意味着$ g $的最低度最多为$ 2D+1 $。我们还表明，获得边缘数量的唯一图形是完整的图形$ k_ {d+2} $。因此，在$ \ d+3 $ vertices上的$ \ mathbb {r}^d $中的每个最小全球刚性图都在$ \ mathbb {r}^{d+1} $中灵活。作为我们对最小全球刚性图的稀疏性的主要结果的对应物，我们表明，在二维中，密集的图始终包含非平凡的全球刚性子图。更确切地说，如果某些图$ g =（v，e）$满足$ | e | \ geq 5 | v | $，则$ g $包含至少七个在$ \ mathbb {r}^2 $中的全球刚性的顶点上的子图。如果众所周知的“足够的连通性猜想”是正确的，那么我们的方法也扩展到更高的维度。最后，我们讨论了对主要结果的猜想加强，该结果指出，如果一对$ \ {u，v \} $在$ g $中链接在$ g $中，则在$ \ mathbb {r}^{d+1} $中，那么$ \ {u，v \} $在$ g $中与$ g $ in Mathbb {u}^$}我们在$ d = 1,2 $案件中证明了这个猜想，以及各种相关结果。
A graph $G = (V,E)$ is globally rigid in $\mathbb{R}^d$ if for any generic placement $p : V \rightarrow \mathbb{R}^d$ of the vertices, the edge lengths $||p(u) - p(v)||, uv \in E$ uniquely determine $p$, up to congruence. In this paper we consider minimally globally rigid graphs, in which the deletion of an arbitrary edge destroys global rigidity. We prove that if $G=(V,E)$ is minimally globally rigid in $\mathbb{R}^d$ on at least $d+2$ vertices, then $|E|\leq (d+1)|V|-\binom{d+2}{2}$. This implies that the minimum degree of $G$ is at most $2d+1$. We also show that the only graph in which the upper bound on the number of edges is attained is the complete graph $K_{d+2}$. It follows that every minimally globally rigid graph in $\mathbb{R}^d$ on at least $d+3$ vertices is flexible in $\mathbb{R}^{d+1}$. As a counterpart to our main result on the sparsity of minimally globally rigid graphs, we show that in two dimensions, dense graphs always contain nontrivial globally rigid subgraphs. More precisely, if some graph $G=(V,E)$ satisfies $|E|\geq 5|V|$, then $G$ contains a subgraph on at least seven vertices that is globally rigid in $\mathbb{R}^2$. If the well-known "sufficient connectivity conjecture" is true, then our methods also extend to higher dimensions. Finally, we discuss a conjectured strengthening of our main result, which states that if a pair of vertices $\{u,v\}$ is linked in $G$ in $\mathbb{R}^{d+1}$, then $\{u,v\}$ is globally linked in $G$ in $\mathbb{R}^d$. We prove this conjecture in the $d=1,2$ cases, along with a variety of related results.
