A357778 - OEIS

%I #17 Feb 18 2024 02:09:10

%S 0,1,3,6,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,85,90,95,100,

%T 105,110,115,120,125,130,135,140,145,150,155,160,165,170,175,180,185,

%U 190,195,200,205,210,215,220,225,230,235

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

%C 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 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 Allan Bickle, Fundamentals of Graph Theory, AMS (2020).

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

%H 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 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 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 a(n) = C(n,2) for n < 7.

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

%e For n < 7, the only maximal 5-degenerate graph is complete.

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

%K nonn

%O 1,3

%A _Allan Bickle_, Oct 13 2022