A357778 Maximum number of edges in a 5-degenerate graph with n vertices.

0, 1, 3, 6, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195, 200, 205, 210, 215, 220, 225, 230, 235

Offset: 1

Author

Allan Bickle, Oct 13 2022

Keywords

• nonn

Comments

A maximal 5-degenerate graph can be constructed from a 5-clique by iteratively adding a new 5-leaf (vertex of degree 5) adjacent to five existing vertices.

This is also the number of edges in a 5-tree with n>5 vertices. (In a 5-tree, the neighbors of a newly added vertex must form a clique.)

Examples

			For n < 7, the only maximal 5-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 < 7.

a(n) = 5*n-15 for n > 4.