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,3

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

References

Allan Bickle, Fundamentals of Graph Theory, AMS (2020).

J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977), 101-106.

Links

Table of n, a(n) for n=1..50.

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

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

Example

For n < 7, the only maximal 5-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: A310077 A310078 A310079 * A168101 A310080 A027920

Adjacent sequences: A357775 A357776 A357777 * A357779 A357780 A357781

Keyword

nonn

Author

Allan Bickle, Oct 13 2022

Status

approved