A060577 -id:A060577 - cp's OEIS frontend

A060576 a(n) = 1 except for a(1) = 0.

1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Vladeta Jovovic, Apr 03 2001

Old name: Number of homeomorphically irreducible general graphs on 1 labeled node and with n edges.
A homeomorphically irreducible general graph is a graph with multiple edges and loops and without nodes of degree 2.
This sequence is also produced by Wolfram's Rule 253 of Elementary Cellular Automaton as a triangle read by rows giving successive states initiated with a single ON (black) cell.  See the Wolfram, Weisstein and Index links below. - Robert Price, Jan 31 2016
Decimal expansion of 91/900. - Elmo R. Oliveira, May 05 2024

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

V. Jovovic, Generating functions for homeomorphically irreducible general graphs on n labeled nodes.
V. Jovovic, Recurrences for the numbers of homeomorphically irreducible general graphs on m labeled nodes and n edges.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
S. Wolfram, A New Kind of Science.
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A003514, A060516, A060533-A060537, A060577-A060581.

1, 0, seq(1, n=2..200); # Wesley Ivan Hurt, Apr 12 2017

a(n)=n!=1 \\ Charles R Greathouse IV, Jun 06 2013

G.f.: (x^2 - x + 1)/(1 - x). a(0)=1, a(1)=0; a(n)=1, n > 1.
E.g.f. for homeomorphically irreducible general graphs with n nodes and k edges is (1 + x*y)^(- 1/2)*exp(- x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k + 1, 2)*exp(- x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.
E.g.f.: e^x - x. - Paul Barry, May 06 2007
a(n) = 1 - binomial(0,n-1). - Arkadiusz Wesolowski, Feb 10 2012

Definition simplified by N. J. A. Sloane, Sep 26 2023

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

Original entry on oeis.org

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

Allan Bickle, Apr 11 2024

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.

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

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).

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

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

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

cp's OEIS Frontend

A060576 a(n) = 1 except for a(1) = 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions