OFFSET
1,5
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
LINKS
Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, Josef Schicho, The number of realizations of a Laman graph, arXiv:1701.05500 [math.AG], 2017.
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
EXAMPLE
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.
MATHEMATICA
Table[Length[LamanGraphs[n]], {n, 3, 7}] (* see link, Christoph Koutschan, May 24 2016 *)
PROG
(nauty with Laman plugin) gensparseg $n -K2 -u #see link
CROSSREFS
KEYWORD
nonn,more,changed
AUTHOR
David S. Newman, Jul 01 2013
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
STATUS
approved