Examples of Graphs¶
Here we list some examples of graphs relevant for Rigidity Theory.
Generalized Double Bananas¶
Definition 55 (Generalized double banana)
For \(d\geq 3\) and \(2\leq t\leq d-1\), the graph \(B_{d,t}\) is defined by putting \(B_{d,t}=(G_1\cup G_2)-e\) where \(G_i\cong K_{d+2}\), \(G_1\cap G_2\cong K_{t}\) and \(e\in E(G_1\cap G_2)\). Note that the graph \(B_{3,2}\) is the well known flexible circuit in the rigidity matroid \(\mathcal{R}_3\), commonly referred to as the double banana.
PyRigi: DoubleBanana()
The family \(\mathcal{B}_{d,d-1}^+\) consists of all graphs of the form \((G_1\cup G_2)-\{e,f,g\}\) where: \(G_1\cong K_{d+3}\) and \(e,f,g\in E(G_1)\); \(G_2\cong K_{d+2}\) and \(e\in E(G_2)\); \(G_1\cap G_2\cong K_{d-1}\); \(e,f,g\) do not all have a common end-vertex; if \(\{f,g\}\subset E(G_1)\setminus E(G_2)\) then \(f,g\) do not have a common end-vertex.
Theorem 35
Suppose \(G\) is a flexible \(\mathcal{R}_d\)-circuit with at most \(d+6\) vertices. Then either
\(d=3\) and \(G\in \{B_{3,2}\}\cup \mathcal{B}_{3,2}^+\) or
\(d\geq 4\) and \(G\in \{B_{d,d-1}\), \(B_{d,d-2}\}\cup \mathcal{B}_{d,d-1}^+\).
References: [GGJN22, Thm 1]
Using the 2-sum lemma we can create one family of generalized bananas in which every element of the family is a \(\mathcal{R}_d\)-circuit.
Definition 56
Define \(\overline B_{d,d-1}\) to be obtained from \(B_{d,d-1}\) by adding back the edge \(e\). It follows that \(\textrm{cl} (B_{d,d-1})=\overline B_{d,d-1}\), and so \(\overline B_{d,d-1}\) is a flexible 2-fold circuit in \(\mathcal{R}_d\). We define the triple banana \(B^{(3)}_{d,d-1}\) to be the 2-sum of \(\overline B_{d,d-1}\) and \(K_{d+2}\) again along \(e\). By the k-sum Lemma, \(B^{(3)}_{d,d-1}\) is a 2-fold circuit in \(\mathcal{R}_d\). Iterating this process, we get that the \((k+1)\)-tuple banana \(B^{(k+1)}_{d,d-1}\) is a \(k\)-fold circuit in \(\mathcal{R}_d\).
\(n\)-Frustum¶
Definition 57 (\(n\)-Frustum)
Assume that \(n\geq 3\). The graph \(G=(V,E)\) is called the \(n\)-Frustum if it is the Cartesian product \(G=C_n\,\square \, K_2\) of a cycle graph \(C_n\) on \(n\) vertices and the complete graph \(K_2\) on two vertices.
As a framework, the \(n\)-Frustum is typically realized as two regular \(n\)-sided polygons on circles centered in the origin of the Euclidean plane with radii \(r_1<r_2\). It has a nontrivial infinitesimal flex given by the rotation of the outer polygon while the inner polygon remains fixed. This infinitesimal flex does not extend to a continuous flex.
Symmetric Graphs¶
Definition 58 (\(C_k\)-symmetric Graph)
Let \(k\geq 4\) be an integer and let \(\Gamma = \langle \gamma \rangle\) denote the multiplicative cyclic group of order \(k\) generated by \(\gamma\in \Gamma\). We use \(c_k\) to denote the anti-clockwise rotation around the origin by \(\frac{2\pi}{k}\). We further denote the isomorphism which maps \(\gamma\) to \(exp(\frac{2\pi i}{k})\) by \(\tau_k:\Gamma \rightarrow \mathcal{C}_k\) for the group \(\mathcal{C}_k\) generated by \(c_k\).
We say that a finite simple graph is \(\Gamma\)-symmetric, if there exists a homomorphism \(\Theta:\Gamma \rightarrow \text{Aut}(G)\). Moreover, we say that a \(2\)-dimensional framework \(F=(G,p)\) on \(G\) is \(\mathcal{C}_k\)-symmetric, if \(G\) is \(\Gamma\)-symmetric and for all \(\delta \in \Gamma\) and \(v\in V(G)\) we have \(\tau_k(\delta)\,p(v) = p(\delta v)\).
References: [LPS24]
Definition 59 (Counterexample for the symmetry-adjusted Laman count with a free group action)
Let \(n\geq8\) be even, and let \(\mathcal{C}_n\) denote the anti-clockwise rotation around the origin by \(2\pi/n\). Define a 4-regular graph \(H_n=(V_n,E_n)\) on the vertex set \(V_n=\{v_1,\dots,v_n\}\) such that each vertex \(v_i\) of \(H_n\) is exactly adjacent to \(v_{i+1}\), \(v_{i-1}\), \(v_{i+3}\) and \(v_{i-3}\) with \(v_{n+k}=v_k\) and \(v_{1-k}=v_{n+1-k}\) for \(k\in \{1,2,3\}\).
Define a framework \((H_n,p)\) on \(H_n\) realized on the unit circle in \(\mathbb{R}^2\) such that \(p(v_1)=\mathcal{C}_np(v_n)\) and \(p(v_i)=\mathcal{C}_np(v_{i-1})\) for all \(2\leq i\leq n\). For some vector \(t\) on the line from the origin to a vertex from \(\{v_1,\dots,v_n\}\), such a framework has a nontrivial infinitesimal motion \(m\) which satisfies the system of equations
where \(1\leq i\leq n\).
PyRigi: CnSymmetricFourRegular()
CnSymmetricFourRegular()
References: [LPS24]
Definition 60 (Counterexample for the symmetry-adjusted Laman count which contains a joint at the origin)
The previous example can be extended in the following way: add a vertex \(u\) and the vertices \(U_n=\{u_1,\dots,u_n\}\) to \(H_n\) from the previous definition. We also add the following edges to \(H_n\):
For all \(1\leq i\leq n\), add the edge \(\{u,u_i\}\).
For all \(1\leq i\leq n\), add the edge \(\{u_i,v_i\}\).
For all \(3\leq i\leq n\), add the edge \(\{u_i,u_{i-2}\}\). Also add the edges \(\{u_1,u_{n-1}\}\) and \(\{u_2,u_n\}\).
Denote the edge set created in this way by \(F_n\). This creates the graph \(G_n=(V_n\cup\{u\}\cup U_n,~E_n \cup F_n)\).
As a framework, this graph can be realized extending the realization \(p:V_n\rightarrow \mathbb{R}^2\) from before to \(G_n\): \(p(u)\) is placed at the origin, and the other \(n\) vertices \(\{p(u_1),\dots,p(u_n)\}\) are placed on a circle with radius \(r>0\) so that that \(p(u_1)=\mathcal{C}_np(u_n)\) and \(p(u_i)=\mathcal{C}_np(u_{i-1})\) for all \(2\leq i\leq n\). In this way, the new edges given in (iii) form two disjoint regular \(n/2\)-gons. The nontrivial infinitesimal motion from the previous example extends to a nontrivial infinitesimal motion of the new framework \((G_n,p)\) which rotates the two \(n/2\)-gons clockwise and anti-clockwise, respectively.
PyRigi: CnSymmetricWithFixedVertex()
CnSymmetricWithFixedVertex()
References: [LPS24]