cp's OEIS Frontend

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

%I A273468 #41 Jun 02 2025 17:58:53
%S A273468 1,1,1,1,3,11,61,499,5500,75635,1237670,23352425,498028767,
%T A273468 11836515526,310152665647,8883427573134
%N A273468 Number of minimally rigid graphs with n vertices constructible by Henneberg type I moves.
%C A273468 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.
%H A273468 L. Henneberg, <a href="https://archive.org/details/diegraphischest00henngoog">Die graphische Statik der starren Systeme</a>, Leipzig, 1911.
%H A273468 Christoph Koutschan, <a href="/A273468/a273468_1.txt">Mathematica program</a>
%H A273468 G. Laman, <a href="http://dx.doi.org/10.1007/BF01534980">On Graphs and Rigidity of Plane Skeletal Structures</a>, Journal of Engineering Mathematics 4 (1970), 331-340.
%H A273468 Martin Larsson, <a href="https://github.com/martinkjlarsson/nauty-laman-plugin">Nauty Laman plugin</a>
%H A273468 Wikipedia, <a href="http://en.wikipedia.org/wiki/Laman_graph">Laman graph</a>
%e A273468 A single vertex is rigid.
%e A273468 The graph consisting of two vertices joined by an edge is rigid.
%e A273468 A triangle is rigid and it is obtained by a single Henneberg type I move.
%e A273468 One more such move yields the only Laman graph with four vertices.
%e A273468 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.
%e A273468 An example of a Laman graph that cannot be constructed using only Henneberg type I moves is the complete bipartite graph K(3,3).
%t A273468 Table[Length[H1LamanGraphs[n]], {n,3,7}]  (* see link *)
%o A273468 (nauty) gensparseg $n -H -u # With Laman plugin; see link.
%Y A273468 Cf. A227117.
%K A273468 nonn,more
%O A273468 1,5
%A A273468 _Christoph Koutschan_, May 23 2016
%E A273468 a(13) added by _Jose Capco_, Dec 07 2018
%E A273468 a(14)-a(15) added by _Martin Larsson_, Dec 21 2020
%E A273468 a(16) from _Martin Larsson_ added by _Max Alekseyev_, Jan 14 2025