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

%I #28 Jun 09 2024 09:02:33

%S 12,36,66,102,144,192,246,306,372,444,522,606,696,792,894,1002,1116,

%T 1236,1362,1494,1632,1776,1926,2082,2244,2412,2586,2766,2952,3144,

%U 3342,3546,3756,3972,4194,4422,4656,4896,5142,5394,5652,5916,6186,6462,6744,7032,7326,7626,7932

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

%C The Zagreb index of a graph is the sum of the squares of the degrees over all vertices of the graph.

%C 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.

%H Paolo Xausa, <a href="/A371912/b371912.txt">Table of n, a(n) for n = 3..10000</a>

%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.

%H Allan Bickle, <a href="https://ajc.maths.uq.edu.au/pdf/89/ajc_v89_p167.pdf">Zagreb Indices of Maximal k-degenerate Graphs</a>, Australas. J. Combin. 89 1 (2024) 167-178.

%H J. Estes and B. Wei, <a href="https://doi.org/10.1007/s10878-012-9515-6">Sharp bounds of the Zagreb indices of k-trees</a>, J Comb Optim 27 (2014), 271-291.

%H I. Gutman and K. Das, <a href="https://match.pmf.kg.ac.rs/electronic_versions/Match50/match50_83-92.pdf">The first Zagreb index 30 years after</a>, MATCH Commun. Math. Comput. Chem. 50 (2004), 83-92.

%H A. Hou, S. Li, L. Song, and B. Wei, <a href="https://link.springer.com/article/10.1007/s10878-010-9288-8">Sharp bounds for Zagreb indices of maximal outerplanar graphs</a>, J Comb Optim 22 (2011), 252-269.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).

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

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

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

%F G.f.: 6*x^3*(2 - x^2)/(1 - x)^3. - _Stefano Spezia_, Apr 12 2024

%F a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 5. - _Chai Wah Wu_, Apr 16 2024

%F 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

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

%t Array[3*(#^2 + # - 8) &, 50, 3] (* _Paolo Xausa_, Jun 09 2024 *)

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

%K nonn,easy

%O 3,1

%A _Allan Bickle_, Apr 11 2024