Spectral radius conditions for the rigidity of graphs

Dandan Fan ; Xueyi Huang ; Huiqiu Lin

The electronic journal of combinatorics, Tome 30 (2023) no. 2

Résumé

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$.

Détail

DOI : 10.37236/11308

Classification : 05C50, 05C62, 05C40, 52C25
Mots-clés : algebraic connectivity, redundant rigidity, global rigidity