Spectral Radius Conditions for the Rigidity of Graphs

[摘要] Rigidity is the property of a structure that does not flex under an applied force. In the past several decades, the rigidity of graphs has been widely studied in discrete geometry and combinatorics. Laman (1970) obtained a combinatorial characterization of rigid graphs in $\mathbb{R}^2$. Lovász and Yemini (1982) proved that every $6$-connected graph is rigid in $\mathbb{R}^2$. Jackson and Jordán (2005) strengthened this result, and showed that every $6$-connected graph is globally rigid in $\mathbb{R}^2$. Thus every graph with algebraic connectivity greater than $5$ is globally rigid in $\mathbb{R}^2$. In 2021, Cioabă, Dewar and Gu improved this bound, and proved that every graph with minimum degree at least $6$ and algebraic connectivity greater than $2+\frac{1}{\delta-1}$ (resp., $2+\frac{2}{\delta-1}$) is rigid (resp., globally rigid) in $\mathbb{R}^2$. In this paper, we study the rigidity of graphs in $\mathbb{R}^2$ from the viewpoint of adjacency eigenvalues. Specifically, we provide a spectral radius condition for the rigidity (resp., globally rigidity) of $2$-connected (resp., $3$-connected) graphs with given minimum degree. Furthermore, we determine the unique graph attaining the maximum spectral radius among all minimally rigid graphs of order $n$.

[学科分类] 统计和概率