The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A328419 Number of minimally rigid graphs in 3D on n vertices. 2
1, 1, 1, 4, 26, 374, 11487, 612884, 48176183 (list; graph; refs; listen; history; text; internal format)



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.


Table of n, a(n) for n=3..11.

Georg Grasegger, Mathematica program: Minimally rigid graphs in 3D with n<=11 vertices

G. Grasegger, C. Koutschan, 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.


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


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

Sequence in context: A063182 A293954 A317668 * A194926 A167147 A322395

Adjacent sequences:  A328416 A328417 A328418 * A328420 A328421 A328422




Georg Grasegger, Oct 28 2019



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 11:38 EDT 2021. Contains 347642 sequences. (Running on oeis4.)