cp's OEIS Frontend

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

%I A357778 #17 Feb 18 2024 02:09:10
%S A357778 0,1,3,6,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,
%T A357778 105,110,115,120,125,130,135,140,145,150,155,160,165,170,175,180,185,
%U A357778 190,195,200,205,210,215,220,225,230,235
%N A357778 Maximum number of edges in a 5-degenerate graph with n vertices.
%C A357778 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.
%C A357778 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.)
%D A357778 Allan Bickle, Fundamentals of Graph Theory, AMS (2020).
%D A357778 J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977), 101-106.
%H A357778 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 A357778 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 A357778 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 A357778 a(n) = C(n,2) for n < 7.
%F A357778 a(n) = 5*n-15 for n > 4.
%e A357778 For n < 7, the only maximal 5-degenerate graph is complete.
%Y A357778 Number of edges in a maximal k-degenerate graph for k=2..6: A004273, A296515, A113127, A357778, A357779.
%K A357778 nonn
%O A357778 1,3
%A A357778 _Allan Bickle_, Oct 13 2022