|
| |
|
|
A273468
|
|
Number of minimally rigid graphs with n vertices constructible by Henneberg type I moves.
|
|
6
|
|
|
|
1, 1, 1, 1, 3, 11, 61, 499, 5500, 75635, 1237670, 23352425, 498028767, 11836515526, 310152665647
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
