Spectral conditions for graph rigidity in the Euclidean plane

Sebastian M. Cioabă, Xiaofeng Gu

Published 2020-01-20Version 1

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 $d$-space. 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\'asz and Yemini discovered a new characterization and proved that every $6$-connected graph is rigid in the Euclidean plane. Consequently, if Fiedler's algebraic connectivity is at least $6$, then $G$ is rigid. In this paper, we show that if $G$ has minimum degree $\delta\geq 6$ and algebraic connectivity greater than $2+\frac{1}{\delta -1}$, then $G$ is rigid. We prove a more general result giving a necessary spectral condition for packing $k$ edge-disjoint spanning rigid subgraphs. The same condition implies that a graph contains $k$ edge-disjoint $2$-connected spanning subgraphs. This result extends previous spectral conditions for packing edge-disjoint spanning trees.