Graph rigidity properties of Ramanujan graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909075137101824 |
|---|---|
| author | Cioabă, Sebastian M. Dewar, Sean Grasegger, Georg Gu, Xiaofeng |
| author_facet | Cioabă, Sebastian M. Dewar, Sean Grasegger, Georg Gu, Xiaofeng |
| contents | A recent result of Cioabă, Dewar and Gu implies that any $k$-regular Ramanujan graph with $k\geq 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_03983 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Graph rigidity properties of Ramanujan graphs Cioabă, Sebastian M. Dewar, Sean Grasegger, Georg Gu, Xiaofeng Combinatorics 52C25 (Primary) 05C50, 05C40 (Secondary) A recent result of Cioabă, Dewar and Gu implies that any $k$-regular Ramanujan graph with $k\geq 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$. |
| title | Graph rigidity properties of Ramanujan graphs |
| topic | Combinatorics 52C25 (Primary) 05C50, 05C40 (Secondary) |
| url | https://arxiv.org/abs/2206.03983 |