OFFSET
1,5
COMMENTS
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.
LINKS
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
Wikipedia, Laman graph
EXAMPLE
A single vertex is rigid.
The graph consisting of two vertices joined by an edge is rigid.
A triangle is rigid and it is obtained by a single Henneberg type I move.
One more such move yields the only Laman graph with four vertices.
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.
An example of a Laman graph that cannot be constructed using only Henneberg type I moves is the complete bipartite graph K(3,3).
MATHEMATICA
Table[Length[H1LamanGraphs[n]], {n, 3, 7}] (* see link *)
PROG
(Nauty with Laman plugin) gensparseg $n -H -u #see link
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Christoph Koutschan, May 23 2016
EXTENSIONS
a(13) added by Jose Capco, Dec 07 2018
a(14)-a(15) added by Martin Larsson, Dec 21 2020
STATUS
approved