A372025 Maximum second Zagreb index of maximal 3-degenerate graphs with n vertices.

12, 54, 120, 210, 324, 462, 624, 810, 1020, 1254, 1512, 1794, 2100, 2430, 2784, 3162, 3564, 3990, 4440, 4914, 5412, 5934, 6480, 7050, 7644, 8262, 8904, 9570, 10260, 10974, 11712, 12474, 13260, 14070, 14904, 15762, 16644, 17550, 18480, 19434, 20412, 21414, 22440, 23490, 24564, 25662, 26784, 27930

Offset

3,1

Comments

The second Zagreb index of a graph is the sum of the products of the degrees over all edges of the graph.

A maximal 3-degenerate graph can be constructed from a 3-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to three existing vertices. The extremal graphs are 3-stars, so the bound also applies to 3-trees.

Links

Table of n, a(n) for n=3..50.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

Allan Bickle, Zagreb Indices of Maximal k-degenerate Graphs, Australas. J. Combin. 89 1 (2024) 167-178.

J. Estes and B. Wei, Sharp bounds of the Zagreb indices of k-trees, J Comb Optim 27 (2014), 271-291.

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Formula

a(n) = 3*(n-1)^2 + 9*(n-3)*(n-1).

From Chai Wah Wu, Apr 16 2024: (Start)

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 5.

G.f.: x^3*(6*x^2 - 18*x - 12)/(x - 1)^3. (End)

a(n) = 6*A014107(n-1). Sum_{n>=3} 1/a(n) = (1/2+log(2))/9 = 0.1325719... - R. J. Mathar, Apr 22 2024

Example

The graph K_3 has 3 degree 2 vertices, so a(3) = 3*4 = 12.

Crossrefs

Cf. A002378, A152811, A371912 (Zagreb indices of maximal k-degenerate graphs).

Cf. A051624, A372025, A372026 (second Zagreb indices of maximal k-degenerate graphs).

Cf. A372027 (second Zagreb index of MOPs).

Sequence in context: A000735 A341558 A022704 * A060785 A059986 A088941

Adjacent sequences: A372022 A372023 A372024 * A372026 A372027 A372029

Keyword

nonn,easy,changed

Author

Allan Bickle, Apr 16 2024

Status

approved