A372026 Minimum second Zagreb index of maximal 2-degenerate graphs with n vertices.

12, 33, 51, 86, 116, 147, 178, 210, 242, 274, 306, 338, 370, 402, 434, 466, 498, 530, 562, 594, 626, 658, 690, 722, 754, 786, 818, 850, 882, 914, 946, 978, 1010, 1042, 1074, 1106, 1138, 1170, 1202, 1234, 1266, 1298, 1330, 1362, 1394, 1426, 1458, 1490, 1522, 1554, 1586, 1618, 1650, 1682, 1714, 1746, 1778, 1810

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 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. The extremal graphs are described in (Bickle 2024).

Links

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

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 (2,-1).

Formula

a(n) = 32*n-110 for n>8.

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

a(n) = 2*a(n-1) - a(n-2) for n > 10.

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

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: A079561 A328326 A131543 * A063296 A372027 A051624

Adjacent sequences: A372023 A372024 A372025 * A372027 A372029 A372030

Keyword

nonn

Author

Allan Bickle, Apr 16 2024

Status

approved