论文标题
欧几里得平面中图刚度的光谱条件
Spectral conditions for graph rigidity in the Euclidean plane
论文作者
论文摘要
刚性是不弯曲的结构的特性。它在离散的几何学和力学中进行了很好的研究，并在材料科学，工程和生物科学中有应用。酒吧和关节框架是Graph $ g $的一对$（G，P）$，将$ G $的顶点的地图$ P $与欧几里得飞机的顶点在一起。我们将$（g，p）$的边缘视为条形，而顶点是通用关节。只要保留了相邻顶点对之间的距离，顶点就可以连续移动。如果任何这样的运动保留了所有对顶点之间的距离，则该框架是刚性的。 1970年，拉曼获得了欧几里得平面中刚性图的组合表征。 1982年，Lovász和Yemini发现了一种新的特征，并证明了每6美元连接的图形都很僵硬。结合全球刚性的特征，它们的证明实际上意味着每个6个连接的图都是全球刚性的。因此，如果Fiedler的代数连接大于5，则$ G $是全球僵化的。 In this paper, we improve this bound and show that for a graph $G$ with minimum degree $δ\geq 6$, if its algebraic connectivity is greater than $2+\frac{1}{δ-1}$, then $G$ is rigid and if its algebraic connectivity is greater than $2+\frac{2}{δ-1}$, then $G$ is globally rigid.我们的结果表明，每一个具有至少$ 8 $学位的连接的常规Ramanujan图都是全球僵化的。 We also prove a more general result giving a sufficient spectral condition for the existence of $k$ edge-disjoint spanning rigid subgraphs.相同的条件意味着图表包含$ K $ edge-disexhint跨度$ 2 $连接的子图。该结果扩展了以前的光谱条件，用于包装边缘跨越树。
Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material science, engineering and biological sciences. A bar-and-joint framework is a pair $(G,p)$ of graph $G$ together with a map $p$ of the vertices of $G$ into the Euclidean plane. We view the edges of $(G, p)$ as bars and the vertices as universal joints. The vertices can move continuously as long as the distances between pairs of adjacent vertices are preserved. The framework is rigid if any such motion preserves the distances between all pairs of vertices. In 1970, Laman obtained a combinatorial characterization of rigid graphs in the Euclidean plane. In 1982, Lovász and Yemini discovered a new characterization and proved that every $6$-connected graph is rigid. Combined with a characterization of global rigidity, their proof actually implies that every 6-connected graph is globally rigid. Consequently, if Fiedler's algebraic connectivity is greater than 5, then $G$ is globally rigid. In this paper, we improve this bound and show that for a graph $G$ with minimum degree $δ\geq 6$, if its algebraic connectivity is greater than $2+\frac{1}{δ-1}$, then $G$ is rigid and if its algebraic connectivity is greater than $2+\frac{2}{δ-1}$, then $G$ is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least $8$ is globally rigid. We also prove a more general result giving a sufficient spectral condition for the existence of $k$ edge-disjoint spanning rigid subgraphs. The same condition implies that a graph contains $k$ edge-disjoint spanning $2$-connected subgraphs. This result extends previous spectral conditions for packing edge-disjoint spanning trees.
