cp's OEIS Frontend

All the minimally rigid graphs on n vertices may be made from the minimally rigid graphs on n-1 vertices by use of two types of constructions called the Henneberg constructions. In the first type a new vertex is added to the graph and two new edges are added connecting the new vertex to two vertices which were already part of the graph. In the second type of construction, two vertices,say v_1 and v_2 which are connected by an edge are selected. Another vertex v_3 is selected. The edge between v_1 and v_2 is deleted. A new vertex w is added to the graph, as well as the edges (v_1,w), (v_2,w),and (v_3,w). Each of these two constructions adds one to the number of vertices and two to the number of edges.

It is known from Pollaczek-Geiringer and Laman that minimally rigid graphs in 2D are exactly the (2,3)-tight graphs. A graph G=(V,E) is (2,3)-tight when |E|=2|V|-3 and for every subgraph G'=(V',E') with at least 2 vertices |E'|<=2|V'|-3. - Georg Grasegger, Sep 17 2024

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The first nontrivial bipartite Laman graph is K_{3,3}. An infinite sequence of such graphs can be obtained from K_{3,3} by Henneberg moves of the first type (i.e., adding a vertex and connecting it with two of the existing vertices from the one part).

The Laman number gives the number of (complex) embeddings of a minimally rigid graph in 2D, modulo translations and rotations, when the edge lengths of the graph are chosen generically. In general, this number is larger than the number of real embeddings. Equivalently, the Laman number of a graph is the number of complex solutions of the quadratic polynomial system {x_1 = y_1 = x_2 = 0, y_2 = l(1,2), (x_i - x_j)^2 + (y_i - y_j)^2 = l(i,j)^2}, for all (i,j) such that the vertices i and j are connected by an edge (w.l.o.g. we assume that there is an edge between the vertices 1 and 2). The quantities l(i,j) correspond to the prescribed edge "lengths" (they can also be complex numbers).

A graph that is constructed only by Henneberg moves of type 1 (i.e., adding one new vertex and connecting it with two existing vertices), has Laman number 2^(n-2). The smallest minimally rigid graph that cannot be constructed in this way, is the 3-prism graph with 6 vertices. Therefore the sequence grows faster than 2^(n-2) for n >= 6.

We know that a graph with n <= 13 vertices achieving the maximal Laman number is unique. We do not know if this is necessarily true for more vertices.

All the Laman graphs (in other words, minimally rigid graphs) can be constructed by the inductive Henneberg construction, i.e., a sequence of Henneberg steps starting from K_2. A new vertex added by a Henneberg move is connected with two or three of the previously existing vertices. Hence, the chromatic number of a Laman graph can be 2, 3 or 4. One can hypothesize that the set of 3-chromatic Laman graphs is the largest and that bipartite graphs are relatively rare. The simplest example of a 4-chromatic Laman graph is the Moser spindle.

A 2n-vertex graph is (3/2,2)-sparse if every subgraph with k vertices has at most (3/2)k-2 edges, and (3/2,2)-tight if in addition it has exactly 3n-2 edges; see Lee and Streinu (2008). These graphs represent two-dimensional mechanical systems formed by 2n rigid bodies (links), connected at joints where exactly two links are pinned together and can rotate relative to each other, with the entire system having one degree of freedom and having no rigid subsystems. The vertices of the graph represent links and the edges represent joints.