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

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, 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, 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

Offset: 3

Author

Allan Bickle, Jun 16 2023

Keywords

• nonn
• easy

Comments

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

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.

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).

Examples

			For n=3, K_3 has irregularity 0, so a(3) = 0.
For n=4, K_4 minus an edge has irregularity 4, so a(4) = 4.
For n=5, K_4 with a subdivided edge has irregularity 2, so a(5) = 2.
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.
		

Links

• Allan Bickle and Zhongyuan Che, Irregularities of Maximal k-degenerate Graphs, Discrete Applied Math. 331 (2023) 70-87.
• Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
• Index entries for linear recurrences with constant coefficients, signature (1).

Crossrefs

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

Programs

Mathematica

PadRight[{0,4,2,6},100,8] (* Paolo Xausa, Nov 29 2023 *)

Formula

a(n) = 8 for n > 6.

G.f.: 2*x^4*(2-x+2*x^2+x^3)/(1-x). - Elmo R. Oliveira, Jul 16 2024