OFFSET
3,4
COMMENTS
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.
It is minimally d-rigid if it is d-rigid but looses this property upon deletion of any edge.
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.
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.
LINKS
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0(1), Article 5, 2024.
Matteo Gallet, Georg Grasegger, Matthias Himmelmann and Jan Legerský, PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks, arXiv:2505.22652 [math.MG], 2025.
Georg Grasegger, Dataset of minimally d-rigid graphs obtained from 0-extensions, 2026.
Georg Grasegger, RigiComp - A Mathematica package for computational rigidity of graphs, 2022.
Martin Larsson, Nauty Laman plugin
PyRigi Developers, Rigidity Theory, 2025.
Walter Whiteley, Some matroids from discrete applied geometry, 1996.
EXAMPLE
The complete graphs on four vertices is the result of a 3-dimensional 0-etxension on the triangle graph.
A 3-dimensional 0-extension from this graph yields the complete graph on five vertices with one edge removed.
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.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Georg Grasegger, Apr 15 2026
STATUS
approved