A372027 Maximum second Zagreb index of maximal outerplanar graphs with n vertices.

12, 33, 61, 96, 135, 181, 233, 291, 355, 425, 501, 583, 671, 765, 865, 971, 1083, 1201, 1325, 1455, 1591, 1733, 1881, 2035, 2195, 2361, 2533, 2711, 2895, 3085, 3281, 3483, 3691, 3905, 4125, 4351, 4583, 4821, 5065, 5315, 5571, 5833, 6101, 6375, 6655, 6941, 7233, 7531

Offset: 3

Author

Allan Bickle, Apr 16 2024

Keywords

• nonn

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 outerplanar graph has all vertices on the exterior region, and all other regions triangles. The extremal graphs are fans, except when n=6. Then the extremal graph is the triangular grid with degrees 4,4,4,2,2,2.

Examples

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

Links

• Paolo Xausa, Table of n, a(n) for n = 3..10000
• 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.
• A. Hou, S. Li, L. Song, and B. Wei, Sharp bounds for Zagreb indices of maximal outerplanar graphs, J Comb Optim 22 (2011), 252-269.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

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

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

Programs

Mathematica

LinearRecurrence[{3, -3, 1}, {12, 33, 61, 96, 135, 181, 233}, 50] (* Paolo Xausa, Jan 22 2025 *)

Formula

a(n) = 3*n^2 + n - 19 when n is not 3 or 6.

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

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

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