cp's OEIS Frontend

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

%I A357779 #16 Feb 18 2024 12:17:37
%S A357779 0,1,3,6,10,15,21,27,33,39,45,51,57,63,69,75,81,87,93,99,105,111,117,
%T A357779 123,129,135,141,147,153,159,165,171,177,183,189,195,201,207,213,219,
%U A357779 225,231,237,243,249,255,261,267,273,279
%N A357779 Maximum number of edges in a 6-degenerate graph with n vertices.
%C A357779 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.
%C A357779 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.)
%D A357779 Allan Bickle, Fundamentals of Graph Theory, AMS (2020).
%D A357779 J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977), 101-106.
%H A357779 Allan Bickle, <a href="https://doi.org/10.7151/dmgt.1637">Structural results on maximal k-degenerate graphs</a>, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
%H A357779 Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H A357779 D. R. Lick and A. T. White, <a href="https://doi.org/10.4153/CJM-1970-125-1">k-degenerate graphs</a>, Canad. J. Math. 22 (1970), 1082-1096.
%F A357779 a(n) = C(n,2) for n < 8.
%F A357779 a(n) = 6*n-21 for n > 5.
%e A357779 For n < 8, the only maximal 6-degenerate graph is complete.
%Y A357779 Number of edges in a maximal k-degenerate graph for k=2..6: A004273, A296515, A113127, A357778, A357779.
%K A357779 nonn
%O A357779 1,3
%A A357779 _Allan Bickle_, Oct 13 2022