Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #34 Sep 18 2024 05:51:45
%S 1,1,1,1,3,11,61,499,5500,75635,1237670,23352425,498028767,
%T 11836515526,310152665647
%N Number of minimally rigid graphs with n vertices constructible by Henneberg type I moves.
%C 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 L. Henneberg, <a href="https://archive.org/details/diegraphischest00henngoog">Die graphische Statik der starren Systeme</a>, Leipzig, 1911.
%H Christoph Koutschan, <a href="/A273468/a273468_1.txt">Mathematica program</a>
%H 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 Martin Larsson, <a href="https://github.com/martinkjlarsson/nauty-laman-plugin">Nauty Laman plugin</a>
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Laman_graph">Laman graph</a>
%e A single vertex is rigid.
%e The graph consisting of two vertices joined by an edge is rigid.
%e A triangle is rigid and it is obtained by a single Henneberg type I move.
%e One more such move yields the only Laman graph with four vertices.
%e 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 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 Table[Length[H1LamanGraphs[n]], {n,3,7}] (* see link *)
%o (Nauty with Laman plugin) gensparseg $n -H -u #see link
%Y Cf. A227117.
%K nonn,more
%O 1,5
%A _Christoph Koutschan_, May 23 2016
%E a(13) added by _Jose Capco_, Dec 07 2018
%E a(14)-a(15) added by _Martin Larsson_, Dec 21 2020