A363705 - OEIS

%I #21 Jul 16 2024 14:24:35

%S 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 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 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 The minimum irregularity of all maximal 2-degenerate graphs with n vertices.

%C The irregularity of a graph is the sum of the differences between the degrees over all edges of the graph.

%C 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 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 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 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 <a href="/index/Rec#order_01">Index entries for linear recurrences with constant coefficients</a>, signature (1).

%F a(n) = 8 for n > 6.

%F G.f.: 2*x^4*(2-x+2*x^2+x^3)/(1-x). - _Elmo R. Oliveira_, Jul 16 2024

%e For n=3, K_3 has irregularity 0, so a(3) = 0.

%e For n=4, K_4 minus an edge has irregularity 4, so a(4) = 4.

%e For n=5, K_4 with a subdivided edge has irregularity 2, so a(5) = 2.

%e 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 PadRight[{0,4,2,6},100,8] (* _Paolo Xausa_, Nov 29 2023 *)

%Y Cf. A002378, A046092, A028896 (irregularities of maximal k-degenerate graphs).

%K nonn,easy

%O 3,2

%A _Allan Bickle_, Jun 16 2023