A273468 Number of minimally rigid graphs with n vertices constructible by Henneberg type I moves.

1, 1, 1, 1, 3, 11, 61, 499, 5500, 75635, 1237670, 23352425, 498028767, 11836515526, 310152665647, 8883427573134

Offset: 1

Author

Christoph Koutschan, May 23 2016

Keywords

• nonn
• more

Comments

A graph is called rigid if, when we fix the length of each edge, it has only finitely many embeddings in the plane. A graph is called minimally rigid (or a Laman graph) if there is no edge that can be omitted while keeping the rigidity property. Laman graphs can be constructed by applying successively Henneberg moves (of type I or type II), starting with the graph that consists of two vertices joined by an edge. Here we consider Laman graphs that can be obtained by using only Henneberg type I moves, which means: adding one vertex and joining it with two different existing vertices.

Examples

			A single vertex is rigid.
The graph consisting of two vertices joined by an edge is rigid.
A triangle is rigid and it is obtained by a single Henneberg type I move.
One more such move yields the only Laman graph with four vertices.
Also all three Laman graphs with five vertices can be constructed with type I moves. Therefore the first five entries of this sequence agree with A227117.
An example of a Laman graph that cannot be constructed using only Henneberg type I moves is the complete bipartite graph K(3,3).
		

Links

• L. Henneberg, Die graphische Statik der starren Systeme, Leipzig, 1911.
• Christoph Koutschan, Mathematica program
• G. Laman, On Graphs and Rigidity of Plane Skeletal Structures, Journal of Engineering Mathematics 4 (1970), 331-340.
• Martin Larsson, Nauty Laman plugin
• Wikipedia, Laman graph

Crossrefs

Cf. A227117.

Programs

Mathematica

Table[Length[H1LamanGraphs[n]], {n,3,7}]  (* see link *)

nauty

gensparseg $n -H -u # With Laman plugin; see link.

Extensions

a(13) added by Jose Capco, Dec 07 2018

a(14)-a(15) added by Martin Larsson, Dec 21 2020

a(16) from Martin Larsson added by Max Alekseyev, Jan 14 2025