Graph rigidity properties of Ramanujan graphs

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

m a t h b b R^{2}

.

Review text

Summary: A recent result of \textit{S. M. Cioabă} et al. [Discrete Math. 344, No. 10, Article ID 112527, 9 p. (2021; Zbl 1469.05102)] implies that any \(k\)-regular Ramanujan graph with \(k \geqslant 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 \textit{M. Morgenstern} in [J. Comb. Theory, Ser. B 62, No. 1, 44--62 (1994; Zbl 0814.68098)] 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\).

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Graph rigidity properties of Ramanujan graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133153)