Abstract
Let Γ= (V, E) be a (non-trivial) finite graph with λ: E→ R+ an edge labeling of Γ. Let ρ: V→ R2 be a map which preserves the edge labeling, i.e., ‖ρ(u)-ρ(v)‖2=λ((u,v)),∀(u,v)∈E,where ‖ x- y‖ 2 denotes the Euclidean distance between two points x, y∈ R2. The labeled graph is said to be flexible if there exists an infinite number of such maps (up to equivalence by rigid transformations) and it is said to be movable if there exists an infinite number of injective maps (again up to equivalence by rigid transformations). We study movability of Cayley graphs and construct regular movable graphs of all degrees. Further, we give explicit constructions of dense, movable graphs.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Annals of Combinatorics |
| Antal sider | 16 |
| ISSN | 0218-0006 |
| DOI | |
| Status | E-pub ahead of print - 2022 |
| Udgivet eksternt | Ja |
Bibliografisk note
Funding Information:I wish to thank the anonymous reviewers for their constructive comments and suggestions which improved the article. I am grateful to Josef Schicho for a number of helpful discussions on rigidity and flexibility of graphs and for his encouragement in pursuing the work. The project was initiated while on a visit to the Johann Radon Institute for Computational and Applied Mathematics (RICAM) and the Johannes Kepler University (JKU), Linz. The author thanks the Fakultät für Mathematik, Universität Wien where his work was supported by the European Research Council (ERC) grant of Goulnara Arzhantseva, “ANALYTIC” grant agreement no. 259527.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Nature Switzerland AG.