Graph rigidity properties of Ramanujan graphs

Abstract

A recent result of Cioabă, Dewar and Gu implies that any $k$-regular Ramanujan graph with $k\ge 8$ is globally rigid in ${\mathbb{R}}^2$. In this paper, we extend these results and prove that any $k$-regular Ramanujan graph of sufficiently large order is globally rigid in ${\mathbb{R}}^2$ when $k\in \{6,7\}$, and when $k\in \{4,5\}$ if it is also vertex-transitive. These results imply that the Ramanujan graphs constructed by Morgenstern in 1994 are globally rigid. We also prove several results on other types of framework rigidity, including body-bar rigidity, body-hinge rigidity, and rigidity on surfaces of revolution. In addition, we use computational methods to determine which Ramanujan graphs of small order are globally rigid in ${\mathbb{R}}^2$.

23 pages, 9 figures

References in corpus (2)

• Spanning rigid subgraph packing and sparse subgraph covering
• Spectral conditions for graph rigidity in the Euclidean plane