A357779 Maximum number of edges in a 6-degenerate graph with n vertices.

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

Author

Allan Bickle, Oct 13 2022

Keywords

• nonn

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

Examples

			For n < 8, the only maximal 6-degenerate graph is complete.
		

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.

Crossrefs

Number of edges in a maximal k-degenerate graph for k=2..6: A004273, A296515, A113127, A357778, A357779.

Formula

a(n) = C(n,2) for n < 8.

a(n) = 6*n-21 for n > 5.