cp's OEIS Frontend

A363705 The minimum irregularity of all maximal 2-degenerate graphs with n vertices.

%I A363705 #21 Jul 16 2024 14:24:35
%S A363705 0,4,2,6,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
%T A363705 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
%U A363705 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
%N A363705 The minimum irregularity of all maximal 2-degenerate graphs with n vertices.
%C A363705 The irregularity of a graph is the sum of the differences between the degrees over all edges of the graph.
%C A363705 A maximal 2-degenerate graph can be constructed from a 2-clique by iteratively adding a new 2-leaf (vertex of degree 2) adjacent to two existing vertices.
%C A363705 This is also the minimum sigma irregularity of all maximal 2-degenerate graphs with n vertices. (The sigma irregularity of a graph is the sum of the squares of the differences between the degrees over all edges of the graph).
%H A363705 Allan Bickle and Zhongyuan Che, <a href="https://doi.org/10.1016/j.dam.2023.01.020">Irregularities of Maximal k-degenerate Graphs</a>, Discrete Applied Math. 331 (2023) 70-87.
%H A363705 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 A363705 <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (1).
%F A363705 a(n) = 8 for n > 6.
%F A363705 G.f.: 2*x^4*(2-x+2*x^2+x^3)/(1-x). - _Elmo R. Oliveira_, Jul 16 2024
%e A363705 For n=3, K_3 has irregularity 0, so a(3) = 0.
%e A363705 For n=4, K_4 minus an edge has irregularity 4, so a(4) = 4.
%e A363705 For n=5, K_4 with a subdivided edge has irregularity 2, so a(5) = 2.
%e A363705 For n>6, add a 2-leaf adjacent to the 2-leaves of the square of a path.  This graph has irregularity 8, so a(n) = 8.
%t A363705 PadRight[{0,4,2,6},100,8] (* _Paolo Xausa_, Nov 29 2023 *)
%Y A363705 Cf. A002378, A046092, A028896 (irregularities of maximal k-degenerate graphs).
%K A363705 nonn,easy
%O A363705 3,2
%A A363705 _Allan Bickle_, Jun 16 2023