Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The rigidity of graphs
HTML articles powered by AMS MathViewer

by L. Asimow and B. Roth PDF
Trans. Amer. Math. Soc. 245 (1978), 279-289 Request permission

Abstract:

We regard a graph G as a set $\{ 1, \ldots , v \}$ together with a nonempty set E of two-element subsets of $\{ 1, \ldots , v \}$. Let $p = ({p_1},\ldots ,{p_v})$ be an element of ${\textbf {R}^{nv}}$ representing v points in ${\textbf {R}^n}$. Consider the figure $G(p)$ in ${\textbf {R}^n}$ consisting of the line segments $[{p_i},{p_j}]$ in ${\textbf {R}^n}$ for $\{ i,j\} \in E$. The figure $G(p)$ is said to be rigid in ${\textbf {R}^n}$ if every continuous path in ${\textbf {R}^{nv}}$, beginning at p and preserving the edge lengths of $G(p)$, terminates at a point $q \in {\textbf {R}^{nv}}$ which is the image $(T{p_1}, \ldots ,T{p_v})$ of p under an isometry T of ${\textbf {R}^n}$. Otherwise, $G(p)$ is flexible in ${\textbf {R}^n}$. Our main result establishes a formula for determining whether $G(p)$ is rigid in ${\textbf {R}^n}$ for almost all locations p of the vertices. Applications of the formula are made to complete graphs, planar graphs, convex polyhedra in ${\textbf {R}^3}$, and other related matters.
References
    D. Barnette and B. Grünbaum, On Steinitz’s theorem concerning convex 3-polytopes and on some properties of planar graphs, The Many Facets of Graph Theory, Lecture Notes in Math., vol. 110, Springer-Verlag, Berlin, 1969, pp. 27-40.
  • Herman Gluck, Almost all simply connected closed surfaces are rigid, Geometric topology (Proc. Conf., Park City, Utah, 1974) Lecture Notes in Math., Vol. 438, Springer, Berlin, 1975, pp. 225–239. MR 0400239
  • G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340. MR 269535, DOI 10.1007/BF01534980
  • John Milnor, Singular points of complex hypersurfaces, Annals of Mathematics Studies, No. 61, Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1968. MR 0239612
  • A. H. Wallace, Algebraic approximation of curves, Canadian J. Math. 10 (1958), 242–278. MR 94355, DOI 10.4153/CJM-1958-028-5
Similar Articles
Additional Information
  • © Copyright 1978 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 245 (1978), 279-289
  • MSC: Primary 57M15; Secondary 05C10, 52A40, 53B50, 73K05
  • DOI: https://doi.org/10.1090/S0002-9947-1978-0511410-9
  • MathSciNet review: 511410