The rigidity of graphs

Abstract

We regard a graph <italic>G</italic> as a set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma ellipsis comma v EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{ 1, \ldots , v \}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> together with a nonempty set <italic>E</italic> of two-element subsets of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma ellipsis comma v EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{ 1, \ldots , v \}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p equals left-parenthesis p 1 comma ellipsis comma p Subscript v Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>v</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p = ({p_1},\ldots ,{p_v})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an element of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n v"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mi>v</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^{nv}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> representing <italic>v</italic> points in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Consider the figure <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> consisting of the line segments <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-bracket p Subscript i Baseline comma p Subscript j Baseline right-bracket"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">[</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">[{p_i},{p_j}]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet i comma j EndSet element-of upper E"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\{ i,j\} \in E</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The figure <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is said to be rigid in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> if every continuous path in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper R Superscript n v"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mi>v</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\textbf {R}^{nv}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, beginning at <italic>p</italic> and preserving the edge lengths of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G left-parenthesis p right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">G(p)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, terminates at a point <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q element-of bold upper R Superscript n v"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext mathvariant="bold">R</mml:mtext> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mi>v</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">q \in {\textbf {R}^{nv}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which is the image <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper T p 1 comma ellipsis comma upper T p Subscript v Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>T</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>T</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>v</mml:mi> </mml