A328419 Number of unlabeled minimally rigid graphs in 3D on n vertices.

1, 1, 1, 4, 26, 374, 11487, 612884, 48176183, 5115840190, 698180921122

Offset: 3

Author

Georg Grasegger, Oct 28 2019

Keywords

• nonn
• more

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.

Every minimally rigid graph in 3D is (3,6)-tight (A374745). - Georg Grasegger, Oct 17 2024

Links

• Georg Grasegger, Mathematica program: Minimally rigid graphs in 3D with n<=11 vertices
• Georg 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.

Crossrefs

Cf. A227117 (number of minimally rigid graphs in 2D on n vertices).

Cf. A374745 (number of (3,6)-tight graphs).

Programs

Mathematica

Table[Length[H12GeiringerGraphs[n]], {n, 4, 11}] (* see Link *)

Extensions

a(12) from Georg Grasegger, independently computed by Martin Larsson, Jan 10 2022

a(13) from Georg Grasegger, Oct 17 2024