OFFSET
3,4
COMMENTS
All minimally rigid graphs in 3D on n vertices can be constructed from the minimally rigid graphs in 3D on n-1 vertices by use of three types of constructions called the Henneberg constructions. In the first type a new vertex is added to the graph and three new edges are added connecting the new vertex to three different vertices which were already part of the graph. In the second type of construction, two adjacent vertices, say v_1 and v_2, are 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), (v_3,w), and (v_4,w), where v_3 and v_4 are other vertices of the graph. The third construction chooses two pairs of adjacent vertices v_1,v_2 and v_3,v_4, where v_3 might be equal to v_2. The edges (v_1,v_2) and (v_3,v_4) are deleted. A new vertex w is added to the graph. If v_2!=v_3, the edges (v_1,w), (v_2,w), (v_3,w), (v_4,w), and (v_5,w) are added, where v_5 is another vertex of the graph. If v_2=v_3, other two vertices v_5,v_6 are chosen and the edges (v_1,w), (v_2,w),(v_4,w), (v_5,w), and (v_6,w) are added.
The first two constructions preserve rigidity whereas the third does not necessarily preserve rigidity. Nevertheless the third construction is needed to get all minimally rigid graphs in 3D. Up to 11 vertices the first two constructions suffice.
Each of these three constructions adds one to the number of vertices and three to the number of edges, i.e., all those graphs have 3n-6 edges for n vertices. Not all graphs with that number of edges are minimally rigid in 3D.
LINKS
G. Grasegger, C. Koutschan and E. Tsigaridas, Lower bounds on the number of realizations of rigid graphs, arXiv:1710.08237 [math.CO], 2017-2018; Experimental Mathematics, 2018 (doi: 10.1080/10586458.2018.1437851).
H. Pollaczek-Geiringer, Zur Gliederungstheorie räumlicher Fachwerke, Zeitschrift für Angewandte Mathematik und Mechanik (ZAMM), 12(1932), 369-376 (doi:10.1002/zamm.19320120606).
Tiong-Seng Tay and Walter Whiteley, Generating Isostatic Frameworks, Structural Topology, 11 (1985), 21-69.
MATHEMATICA
Table[Length[H12GeiringerGraphs[n]], {n, 4, 11}] (* see Link *)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Georg Grasegger, Oct 28 2019
EXTENSIONS
a(12) from Georg Grasegger, independently computed by Martin Larsson, Jan 10 2022
STATUS
approved