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, 285, 291, 297, 303, 309, 315, 321, 327, 333, 339

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

Andrew Howroyd, Table of n, a(n) for n = 1..1000

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.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

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

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

G.f.: x^2*(1 + x)*(1 - x + x^2)*(1 + x + x^2)/(1 - x)^2. - Andrew Howroyd, Nov 23 2025

Example

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

Mathematica

A357779[n_]:= If[n < 6, Binomial[n, 2], 6*n - 21]; Array[A357779, 60] (* or *)
LinearRecurrence[{2, -1}, {0, 1, 3, 6, 10, 15, 21}, 60] (* Paolo Xausa, Feb 07 2026 *)

Prog

(PARI) a(n) = if(n<6, binomial(n, 2), 6*n - 21) \\ Andrew Howroyd, Nov 23 2025

Crossrefs

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

Sequence in context: A376211 A056150 A310081 * A240443 A033439 A194082

Adjacent sequences: A357776 A357777 A357778 * A357780 A357781 A357782

Keyword

nonn,easy

Author

Allan Bickle, Oct 13 2022

Extensions

More terms from Andrew Howroyd, Nov 23 2025

Status

approved