A305132 -id:A305132 - cp's OEIS frontend

A112410 Number of connected simple graphs with n vertices, n+1 edges, and vertex degrees no more than 4.

0, 0, 0, 1, 5, 17, 56, 182, 573, 1792, 5533, 16977, 51652, 156291, 470069, 1407264, 4193977, 12451760, 36838994, 108656009, 319583578, 937634011, 2744720126, 8018165821, 23379886511, 68056985580, 197800670948, 574068309840, 1663907364480, 4816910618093, 13929036720057

Offset: 1

Jonathan Vos Post, Dec 08 2005

nonn

Such graphs are also referred to (e.g., by Hendrickson & Parks) as carbon skeletons with two rings, or bicyclic skeletons, although actual number of simple cycles in such graphs can exceed 2 (e.g., in the example). - Andrey Zabolotskiy, Nov 24 2017

Terms computed with nauty agree at least to a(20) with those computed by formula and sequences A125669, A125670, A125671, A305132. - Andrew Howroyd, May 26 2018

			The only such graph for n = 4 is:
o-o
|/|
o-o

Andrew Howroyd, Table of n, a(n) for n = 1..200
J. B. Hendrickson and C. A. Parks, Generation and Enumeration of Carbon skeletons, J. Chem. Inf. Comput. Sci., 31 (1991), 101-107. See Table 2, column 2 on page 103.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs.

The analogs for n+k edges with k = -1, 0, ..., 7 are: A000602, A036671, this sequence, A112619, A112408, A112424, A112425, A112426, A112442.
Cf. A121941 (any number of edges), A006820 (2n edges).
Cf. A125669, A125670, A125671, A305132.

for n in {4..15}; do geng -c -D4 ${n} $((n+1)):$((n+1)) -u; done # Andrey Zabolotskiy, Nov 24 2017

a(n) = A125669(n) + A125670(n) + A125671(n) + A305132(n). - Andrew Howroyd, May 26 2018

Corrected offset and new name from Andrey Zabolotskiy, Nov 20 2017
a(20) corrected by Andrey Zabolotskiy and Andrew Howroyd, May 26 2018
Terms a(21) and beyond from Andrew Howroyd, May 26 2018

A121331 Number of bridged bicyclic skeletons with n carbon atoms (see Parks et al. for precise definition).

Original entry on oeis.org

1, 2, 6, 15, 39, 99, 258, 671, 1762, 4657, 12372, 33036, 88590, 238483, 644045, 1744542, 4737341, 12894158, 35165994, 96083192, 262951511, 720685274, 1977846334, 5434588909, 14949284828, 41163690109, 113451949753, 312955174089, 863965424349, 2386874582238

Offset: 5

N. J. A. Sloane, Aug 27 2006

nonn

Equivalently, the number of connected graphs on n unlabeled nodes with exactly 2 cycles of the same even length joined along half their length and all nodes having degree at most 4. The resulting graph will have three equal length cycles. - Andrew Howroyd, May 25 2018

			From _Andrew Howroyd_, May 25 2018: (Start)
Illustration of graphs for n=5 and n=6:
    o          o--o       o
   /|\        /|\        /|\
  o o o      o o o      o o o--o
   \|/        \|/        \|/
    o          o          o
.
Illustration of graphs for n=7:
    o--o      o--o--o   o--o        o        o          o   o
   /|\       /|\       /|\         /|\      /|\        /|\ /
  o o o     o o o     o o o--o    o o o    o o o--o   o o o
   \|/       \|/       \|/       / \|/ \    \|/   |    \|/ \
    o--o      o         o       o   o   o    o    o     o   o
(End)

Andrew Howroyd, Table of n, a(n) for n = 5..200
Camden A. Parks and James B. Hendrickson, Enumeration of monocyclic and bicyclic carbon skeletons, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991).

Cf. A121158, A121162, A121165, A305132.

G[n_] := Module[{g}, g[] = 0; Do[g[x] = 1 + x*(g[x]^3/6 + g[x^2]*g[x]/2 + g[x^3]/3) + O[x]^n // Normal, {n}]; g[x]];
C1[n_] := Sum[(d1^(3*k)+3*d1^k*d2^k + 2*d3^k), {k, 1, Quotient[n, 3]}]/12;
C2[n_] := Sum[(d1^Mod[k, 2]*d2^Quotient[k, 2])^3 + 3*d1^Mod[k, 2]* d2^(Quotient[k, 2] + k) + 2*d3^Mod[k, 2]*d6^Quotient[k, 2], {k, 1, Quotient[n, 3]}]/12;
seq[n_] := Module[{s, d, g}, s = G[n]; d = x*(s^2 + (s /. x -> x^2))/2; g[p_, e_] := Normal[(p+O[x]^(Quotient[n, e]+1))] /. x :> x^e; g[s, 1]^2* (C1[n-2] /. Thread[{d1, d2, d3} :> {g[d, 1], g[d, 2], g[d, 3]}]) + g[s, 2]*(C2[n-2] /. Thread[{d1, d2, d3, d6} :> {g[d, 1], g[d, 2], g[d, 3], g[d, 6]}]) + O[x]^n] // CoefficientList[#, x]& // Drop[#, 3]&;
seq[33] (* Jean-François Alcover, Sep 08 2019, after Andrew Howroyd *)

\\ here G is A000598 as series
G(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g, x, x^2)*g/2 + subst(g, x, x^3)/3) + O(x^n)); g}
C1(n)={sum(k=1, n\3, (d1^(3*k) + 3*d1^k*d2^k + 2*d3^k))/12}
C2(n)={sum(k=1, n\3, (d1^(k%2)*d2^(k\2))^3 + 3*d1^(k%2)*d2^(k\2+k) + 2*d3^(k%2)*d6^(k\2))/12}
seq(n)={my(s=G(n)); my(d=x*(s^2+subst(s, x, x^2))/2); my(g(p,e)=subst(p + O(x*x^(n\e)), x, x^e)); Vec(O(x^n/x) + g(s,1)^2*substvec(C1(n-2),[d1,d2,d3],[g(d,1), g(d,2), g(d,3)]) + g(s,2)*substvec(C2(n-2), [d1,d2,d3,d6], [g(d,1), g(d,2), g(d,3), g(d,6)]))} \\ Andrew Howroyd, May 25 2018

a(n) ~ c * d^n / sqrt(n), where d = 1/A261340 = 2.815460033176150746526616778..., c = 0.0064202170754... . - Vaclav Kotesovec, Sep 08 2019

Corrected by Franklin T. Adams-Watters and T. D. Noe, Oct 25 2006

a(24) corrected and terms a(26) and beyond from Andrew Howroyd, May 25 2018

cp's OEIS Frontend

A112410 Number of connected simple graphs with n vertices, n+1 edges, and vertex degrees no more than 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

Extensions