OFFSET
1,3
COMMENTS
A maximal 6-degenerate graph can be constructed from a 6-clique by iteratively adding a new 6-leaf (vertex of degree 6) adjacent to six existing vertices.
This is also the number of edges in a 6-tree with n>6 vertices. (In a 6-tree, the neighbors of a newly added vertex must form a clique.)
REFERENCES
Allan Bickle, Fundamentals of Graph Theory, AMS (2020).
J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977), 101-106.
LINKS
Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
D. R. Lick and A. T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082-1096.
FORMULA
a(n) = C(n,2) for n < 8.
a(n) = 6*n-21 for n > 5.
EXAMPLE
For n < 8, the only maximal 6-degenerate graph is complete.
CROSSREFS
KEYWORD
nonn
AUTHOR
Allan Bickle, Oct 13 2022
STATUS
approved