login
A357779
Maximum number of edges in a 6-degenerate graph with n vertices.
2
0, 1, 3, 6, 10, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99, 105, 111, 117, 123, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279
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
Number of edges in a maximal k-degenerate graph for k=2..6: A004273, A296515, A113127, A357778, A357779.
Sequence in context: A376211 A056150 A310081 * A240443 A033439 A194082
KEYWORD
nonn
AUTHOR
Allan Bickle, Oct 13 2022
STATUS
approved