A395194 - OEIS

%I #4 Apr 21 2026 00:35:24

%S 1,1,1,3,18,235,5919,238723,13546836,1012434730

%N Number of unlabeled minimally 3-rigid graphs on n vertices obtained from 0-extensions.

%C A graph G is d-rigid, if every generic realization p in dimension d yields a framework (G,p) that is infinitesimally d-rigid; i.e., all its infinitesimal flexes are trivial.

%C It is minimally d-rigid if it is d-rigid but looses this property upon deletion of any edge.

%C A d-dimensional 0-extension of a graph adds a new vertex and connects it to d vertices from the original graph. If the original graph is minimally d-rigid, so is the graph obtained from the 0-extension.

%C The sequence counts graphs that can be obtained from 3-dimensional 0-extensions starting with the complete graph on 3 vertices. These are also known as maximal 3-degenerate graphs.

%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0(1), Article 5, 2024.

%H Matteo Gallet, Georg Grasegger, Matthias Himmelmann and Jan Legerský, <a href="https://doi.org/10.48550/arXiv.2505.22652">PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks</a>, arXiv:2505.22652 [math.MG], 2025.

%H Georg Grasegger, <a href="https://doi.org/10.5281/zenodo.18570095">Dataset of minimally d-rigid graphs obtained from 0-extensions</a>, 2026.

%H Georg Grasegger, <a href="https://doi.org/10.5281/zenodo.7457820">RigiComp - A Mathematica package for computational rigidity of graphs</a>, 2022.

%H Martin Larsson, <a href="https://github.com/martinkjlarsson/nauty-laman-plugin">Nauty Laman plugin</a>

%H PyRigi Developers, <a href="https://pyrigi.github.io/PyRigi/math/rigidity.html">Rigidity Theory</a>, 2025.

%H Walter Whiteley, <a href="https://doi.org/10.1090/conm/197">Some matroids from discrete applied geometry</a>, 1996.

%e The complete graphs on four vertices is the result of a 3-dimensional 0-etxension on the triangle graph.

%e A 3-dimensional 0-extension from this graph yields the complete graph on five vertices with one edge removed.

%e There are three graphs that can be obtained from the previous one by adding a new vertex and connecting it to 3 of the existing vertices.

%Y Cf. A273468, A328419.

%K nonn,more

%O 3,4

%A _Georg Grasegger_, Apr 15 2026