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

1, 1, 1, 1, 3, 13, 70, 608, 7222, 110132, 2039273, 44176717, 1092493042, 30322994747, 932701249291

Offset: 1

Author

David S. Newman, Jul 01 2013

Keywords

• nonn
• more

Comments

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

Examples

			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.
		

Links

• Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho, The number of realizations of a Laman graph, arXiv:1701.05500 [math.AG], 2017-2018.
• 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
• David S. Newman, Mathematica program
• H. Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik, Volume 7, Issue 1, 1927, Pages 58-72.
• Eric Weisstein's World of Mathematics, Laman Graph
• Wikipedia, Laman graph

Crossrefs

Cf. A273468, A328060, A328419.

Programs

Mathematica

Table[Length[LamanGraphs[n]], {n, 3, 7}]  (* see link, Christoph Koutschan, May 24 2016 *)

nauty

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

Extensions

a(8) corrected and a(9)-a(12) added by Christoph Koutschan, May 24 2016

a(12) corrected and a(13) computed by Jose Capco added by Christoph Koutschan, Nov 21 2018

Name clarified by Nike Dattani, Sep 28 2019

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