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

12, 36, 66, 102, 144, 192, 246, 306, 372, 444, 522, 606, 696, 792, 894, 1002, 1116, 1236, 1362, 1494, 1632, 1776, 1926, 2082, 2244, 2412, 2586, 2766, 2952, 3144, 3342, 3546, 3756, 3972, 4194, 4422, 4656, 4896, 5142, 5394, 5652, 5916, 6186, 6462, 6744, 7032, 7326, 7626, 7932

Offset: 3

Author

Allan Bickle, Apr 11 2024

Keywords

• nonn
• easy

Comments

The Zagreb index of a graph is the sum of the squares of the degrees over all vertices 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.

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.
• I. Gutman and K. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004), 83-92.
• 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).

Programs

Mathematica

Array[3*(#^2 + # - 8) &, 50, 3] (* Paolo Xausa, Jun 09 2024 *)

Formula

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

a(n) = 6*A046691(n-2) for n>2.

a(n) = 6*A060577(n-1) for n>3.

G.f.: 6*x^3*(2 - x^2)/(1 - x)^3. - Stefano Spezia, Apr 12 2024

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 5. - Chai Wah Wu, Apr 16 2024

Sum_{n>=3} 1/a(n) = 19/72 + Pi*tan(Pi*sqrt(33)/2)*sqrt(33)/99 = 0.1865497.... - R. J. Mathar, Apr 22 2024