OFFSET
4,4
COMMENTS
A graph is d-degenerate if every induced subgraph has minimum degree at most d. It is maximal d-degenerate if by adding any edge the property of being d-degenerate is lost.
Maximal d-degenerate graphs can be obtained from d-dimensional 0-extensions starting with the complete graph on d vertices.
A d-dimensional 0-extension of a graph adds a new vertex and connects it to d exsisting vertices.
Maximal d-degenerate graphs are exactly the minimally d-rigid graphs obtained from d-dimensional 0-extensions.
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.
If the original graph is minimally d-rigid, so is the graph obtained from the 0-extension.
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 five vertices is the result of a 4-dimensional 0-etxension on the complete graph on four vertices. A 4-dimensional 0-extension from this graph yields a complete graph on six 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 4 of the existing vertices.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Georg Grasegger, Apr 21 2026
STATUS
approved