A125670 -id:A125670 - 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

A125669 Number of bicyclic skeletons with n carbon atoms and the parameter 'alpha' having the value of 0. See the paper by Hendrickson and Parks for details.

Original entry on oeis.org

1, 4, 20, 76, 288, 1005, 3433, 11324, 36712, 116809, 367076, 1140226, 3510491, 10722708, 32539364, 98178211, 294767639, 881147521, 2623934079, 7787024985, 23039064263, 67977412951, 200072442611, 587532484513, 1721812143140, 5036454320102, 14706743476128

Offset: 6

Parthasarathy Nambi, Jan 29 2007

nonn

Here 'alpha' is the number of atoms the two rings have in common.

Equivalently, the number of connected graphs on n unlabeled nodes with exactly 2 cycles without any shared node and all nodes having degree at most 4. See A121162 for the special case of the two cycles having the same length. - Andrew Howroyd, May 25 2018

			If n=6 then the number of bicyclics when 'alpha' = zero is 1.
If n=7 then the number of bicyclics when 'alpha' = zero is 4.
If n=8 then the number of bicyclics when 'alpha' = zero is 20.
If n=9 then the number of bicyclics when 'alpha' = zero is 76.
From _Andrew Howroyd_, May 25 2018: (Start)
Case n=7: illustrations of the 4 graphs:
     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 = 6..200
J. B. Hendrickson and C. A. Parks, Generation and Enumeration of Carbon skeletons, J. Chem. Inf. Comput. Sci., 31 (1991), pp. 101-107. See Table VII column 2 on page 104.

Cf. A121162, A121330, A121331, A121332, A121333, A125064, A125670.

\\ 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(i=1, n\2-1, sum(j=1, n\2-i, (d1^(2*(i+j)) + 2*d1^(2*i)*d2^j + d2^(i+j))*(1 + d1)^2))/(8*(1-d1))}
C2(n)={sum(k=1, n\4,  2*(d2^(2*k) + d4^k)*(1 + d2))*(1+d1)/(8*(1-d2))}
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],[g(d,1),g(d,2)]) + g(s,2)*substvec(C2(n-2), [d1,d2,d4], [g(d,1),g(d,2),g(d,4)]))} \\ Andrew Howroyd, May 25 2018

Terms a(16) and beyond from Andrew Howroyd, May 25 2018

A125671 Number of bicyclic skeletons with n carbon atoms and the parameter 'alpha' having the value of 2. See the paper by Hendrickson and Parks for details.

Original entry on oeis.org

1, 3, 11, 32, 100, 294, 881, 2590, 7639, 22344, 65278, 189832, 550846, 1593558, 4600435, 13251623, 38104280, 109382300, 313543725, 897588156, 2566575323, 7331196543, 20921299025, 59653124923, 169959192844, 483897197563, 1376848221698, 3915320424705, 11128029239672

Offset: 4

Parthasarathy Nambi, Jan 29 2007

nonn

Here 'alpha' is the number of atoms the two rings have in common.

Equivalently, the number of connected graphs on n unlabeled nodes with exactly 2 cycles joined at a single edge and all nodes having degree at most 4. See A121165 for the special case of the two cycles having the same length. - Andrew Howroyd, May 25 2018

			If n=5 then the number of bicyclics when 'alpha' = two is 3.
If n=6 then the number of bicyclics when 'alpha' = two is 11.
If n=7 then the number of bicyclics when 'alpha' = two is 32.
If n=8 then the number of bicyclics when 'alpha' = two is 100.
Case n=5: illustration of the 3 graphs:
.
       o---o        o---o       o   o
      /|   |       /|\         /|\  |
     / |   |      / | \       / | \ |
    /  |   |     /  |  \     /  |  \|
   o---o---o    o---o---o   o---o---o

Andrew Howroyd, Table of n, a(n) for n = 4..200
J. B. Hendrickson and C. A. Parks, Generation and Enumeration of Carbon skeletons, J. Chem. Inf. Comput. Sci., 31 (1991), pp. 101-107. See Table VII column 4 on page 104.

Cf. A121165, A121330, A121331, A121332, A121333, A125064, A125670.

\\ 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=2, n, (k-1)*d1^k) + sum(k=1, n\2, d2^k))/4}
C2(n)={(sum(k=1, n\2, d2^k) + sum(i=1, n-1, sum(j=1, n-i, d2^(i\2+j\2) * d1^(i%2+j%2))))/4}
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],[g(d,1),g(d,2)]) + g(s,2)*substvec(C2(n-2), [d1,d2,d4], [g(d,1),g(d,2),g(d,4)]))} \\ Andrew Howroyd, May 25 2018

a(4) prepended and terms a(16) and beyond from Andrew Howroyd, May 25 2018

A305132 Number of connected graphs on n unlabeled nodes with exactly 2 cycles joined along two or more edges but not more than half each cycle and all nodes having degree at most 4.

Original entry on oeis.org

1, 3, 11, 36, 116, 366, 1151, 3583, 11093, 34141, 104489, 318139, 963899, 2907276, 8731919, 26125538, 77889504, 231466147, 685811867, 2026481941, 5973064855, 17565416721, 51547293439, 150977445294, 441409701444, 1288409915625, 3754926609800, 10927779696264

Offset: 5

Andrew Howroyd, May 26 2018

nonn

The resulting graph will actually have three cycles. See A121331 for the special case of all three cycles having the same length.

Equivalently, the number of connected simple graphs with n unlabeled nodes and n + 1 edges and all nodes having degree at most 4 (A112410) less those graphs described by A125669, A125670 and A125671.

			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 o  |
   \|/        \|/        \|/         \|  |
    o          o          o           o--o

Andrew Howroyd, Table of n, a(n) for n = 5..200

Cf. A112410, A121331, A125669, A125670, A125671, A125672, A125673.

\\ 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)={subst(Pol(x^3*d1^3/(1-x*d1)^3 + 3*x^3*d1*d2/((1-x*d1)*(1-x^2*d2)) + 2*x^3*d3/(1-x^3*d3) + O(x*x^n)), x, 1)/12}
C2(n)={subst(Pol(((x*d1+x^2*d2)/(1-x^2*d2))^3 + 3*(x*d1+x^2*d2)*x^2*d2/(1-x^2*d2)^2 + 2*(x^3*d3 + x^6*d6)/(1-x^6*d6) + O(x*x^n)), x, 1)/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)]))}

a(n) >= A125672(n) + A125673(n).

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

A125669 Number of bicyclic skeletons with n carbon atoms and the parameter 'alpha' having the value of 0. See the paper by Hendrickson and Parks for details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A125671 Number of bicyclic skeletons with n carbon atoms and the parameter 'alpha' having the value of 2. See the paper by Hendrickson and Parks for details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A305132 Number of connected graphs on n unlabeled nodes with exactly 2 cycles joined along two or more edges but not more than half each cycle and all nodes having degree at most 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula