OFFSET
3,2
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).
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).
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
EXAMPLE
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.
MATHEMATICA
PadRight[{0, 4, 2, 6}, 100, 8] (* Paolo Xausa, Nov 29 2023 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Allan Bickle, Jun 16 2023
STATUS
approved