|
| |
|
|
A227117
|
|
Number of minimally rigid graphs in 2D on n vertices.
|
|
8
|
|
|
|
1, 1, 1, 1, 3, 13, 70, 608, 7222, 110132, 2039273, 44176717, 1092493042, 30322994747, 932701249291
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
