cp's OEIS Frontend

A227117 Number of minimally rigid graphs in 2D on n vertices.

%I A227117 #92 Jun 02 2025 16:30:28
%S A227117 1,1,1,1,3,13,70,608,7222,110132,2039273,44176717,1092493042,
%T A227117 30322994747,932701249291
%N A227117 Number of minimally rigid graphs in 2D on n vertices.
%C A227117 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.
%C A227117 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
%H A227117 Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, <a href="https://doi.org/10.1137/17M1118312">The number of realizations of a Laman graph</a>, <a href="https://doi.org/10.48550/arXiv.1701.05500">arXiv:1701.05500</a> [math.AG], 2017-2018.
%H A227117 L. Henneberg, <a href="https://archive.org/details/diegraphischest00henngoog">Die graphische Statik der starren Systeme</a>, Leipzig, 1911.
%H A227117 Christoph Koutschan, <a href="/A227117/a227117_2.txt">Mathematica program</a>
%H A227117 G. Laman, <a href="http://doi.org/10.1007/BF01534980">On Graphs and Rigidity of Plane Skeletal Structures</a>, Journal of Engineering Mathematics 4 (1970), 331-340.
%H A227117 Martin Larsson, <a href="https://github.com/martinkjlarsson/nauty-laman-plugin">Nauty Laman plugin</a>
%H A227117 David S. Newman, <a href="/A227117/a227117.txt">Mathematica program</a>
%H A227117 H. Pollaczek-Geiringer, <a href="https://doi.org/10.1002/zamm.19270070107">Über die Gliederung ebener Fachwerke</a>, Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, Volume 7, Issue 1, 1927, Pages 58-72.
%H A227117 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LamanGraph.html">Laman Graph</a>
%H A227117 Wikipedia, <a href="http://en.wikipedia.org/wiki/Laman_graph">Laman graph</a>
%e A227117 A single vertex is rigid, as is two vertices joined by an edge, as is a triangle consisting of three vertices joined pairwise by edges.  So a(1)=a(2)=a(3)=1.  Either of the constructions when applied to the triangle will give a graph consisting of two triangles joined along one side.  Another way to picture this is a square together with one of its diagonals.  Applying the two constructions to this graph gives six graphs, but only three distinct graphs up to graph isomorphism.
%t A227117 Table[Length[LamanGraphs[n]], {n, 3, 7}]  (* see link, _Christoph Koutschan_, May 24 2016 *)
%o A227117 (nauty) gensparseg $n -K2 -u # With Laman plugin; see link.
%Y A227117 Cf. A273468, A328060, A328419.
%K A227117 nonn,more
%O A227117 1,5
%A A227117 _David S. Newman_, Jul 01 2013
%E A227117 a(8) corrected and a(9)-a(12) added by _Christoph Koutschan_, May 24 2016
%E A227117 a(12) corrected and a(13) computed by _Jose Capco_ added by _Christoph Koutschan_, Nov 21 2018
%E A227117 Name clarified by _Nike Dattani_, Sep 28 2019
%E A227117 a(14)-a(15) added by _Martin Larsson_, Dec 21 2020