A395410 - OEIS

%I #9 Jun 09 2026 08:44:15

%S 1,1,1,3,22,488,27376,2955486,512457676,130095650766

%N Number of unlabeled maximal 4-degenerate graphs on n vertices.

%C 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.

%C Maximal d-degenerate graphs can be obtained from d-dimensional 0-extensions starting with the complete graph on d vertices.

%C A d-dimensional 0-extension of a graph adds a new vertex and connects it to d exsisting vertices.

%C Maximal d-degenerate graphs are exactly the minimally d-rigid graphs obtained from d-dimensional 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 If the original graph is minimally d-rigid, so is the graph obtained from the 0-extension.

%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 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.

%Y Cf. A273468, A395194, A394820.

%K nonn,more

%O 4,4

%A _Georg Grasegger_, Apr 21 2026