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

A305059 Triangle read by rows: T(n,k) is the number of connected unicyclic graphs on n unlabeled nodes with cycle length k and all nodes having degree at most 4.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 6, 4, 1, 1, 15, 8, 4, 1, 1, 33, 24, 9, 5, 1, 1, 83, 55, 28, 12, 5, 1, 1, 196, 147, 71, 40, 13, 6, 1, 1, 491, 365, 198, 106, 47, 16, 6, 1, 1, 1214, 954, 521, 317, 136, 63, 18, 7, 1, 1, 3068, 2431, 1418, 868, 428, 190, 73, 21, 7, 1, 1

Offset: 3

Andrew Howroyd, May 24 2018

Equivalently, the number of monocyclic skeletons with n carbon atoms and a ring size of k.

			Triangle begins:
     1;
     1,   1;
     3,   1,   1;
     6,   4,   1,   1;
    15,   8,   4,   1,   1;
    33,  24,   9,   5,   1,  1;
    83,  55,  28,  12,   5,  1,  1;
   196, 147,  71,  40,  13,  6,  1, 1;
   491, 365, 198, 106,  47, 16,  6, 1, 1;
  1214, 954, 521, 317, 136, 63, 18, 7, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 3..1178 (rows n = 3..50)
Camden A. Parks and James B. Hendrickson, Enumeration of monocyclic and bicyclic carbon skeletons, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991).
Eric Weisstein's World of Mathematics, Unicyclic Graph

Columns 3..10 are A063832, A116719, A120333, A120779, A120790, A120795, A121156, A121157.
Row sums are A036671.
Cf. A000598.

G[n_] := Module[{g}, 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]];
T[n_, k_] := Module[{t = G[n], g}, t = x*((t^2 + (t /. x -> x^2))/2); g[e_] = (Normal[t + O[x]^Quotient[n, e]] /. x -> x^e) + O[x]^n // Normal; Coefficient[(Sum[EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[ k], g[1]*g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2])/2, x, n]];
Table[T[n, k], {n, 3, 13}, {k, 3, n}] // Flatten (* Jean-François Alcover, Jul 03 2018, 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}
T(n,k)={my(t=G(n)); t=x*(t^2+subst(t, x, x^2))/2; my(g(e)=subst(t + O(x*x^(n\e)), x, x^e) + O(x*x^n)); polcoeff((sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2, n)}

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

Original entry on oeis.org

0, 0, 0, 0, 2, 14, 79, 430, 2161, 10162, 45282, 192945, 790849, 3138808, 12116550, 45675153, 168661704, 611701138, 2183635232, 7686541342, 26720976964, 91856241351, 312594121721, 1054104924270

Offset: 1

Jonathan Vos Post, Dec 21 2005

nonn

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 4 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, A112410, A112619, this sequence, A112424, A112425, A112426, A112442. Cf. A121941.

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

Corrected offset, new name, and a(18) from Andrey Zabolotskiy, Nov 24 2017

a(18)-a(24) added by Georg Grasegger, Jun 05 2023

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

Original entry on oeis.org

0, 0, 0, 0, 1, 8, 59, 427, 2768, 16461, 90111, 460699, 2222549, 10216607, 45076266, 192059940, 794088479, 3198709835, 12593964702, 48596474890, 184195614359, 687087962550, 2526421534903

Offset: 1

Jonathan Vos Post, Dec 21 2005

nonn

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 5 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, A112410, A112619, A112408, this sequence, A112425, A112426, A112442. Cf. A121941.

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

Corrected offset and new name from Andrey Zabolotskiy, Nov 24 2017

a(16)-a(23) added by Georg Grasegger, Jun 05 2023

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

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 31, 298, 2616, 20346, 140605, 880737, 5082279, 27402524, 139587885, 677772953, 3158930531, 14212444473, 62009204208, 263350765116, 1092085621098, 4433596269478

Offset: 1

Jonathan Vos Post, Dec 21 2005

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 6 on page 103.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs. [gives different a(15)]

The analogs for n+k edges with k = -1, 0, ..., 7 are: A000602, A036671, A112410, A112619, A112408, A112424, this sequence, A112426, A112442. Cf. A121941.

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

Corrected offset and new name from Andrey Zabolotskiy, Nov 24 2017

a(15) corrected and a(16)-a(22) added by Georg Grasegger, Jun 05 2023

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

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 9, 134, 1714, 18436, 167703, 1327240, 9372119, 60324933, 359730035, 2012733260, 10670975762, 54028108819, 262872075003, 1235323112178, 5630370812614

Offset: 1

Jonathan Vos Post, Dec 21 2005

Distribution of carbon skeletons. See the paper by Hendrikson and Parks for details. If n=6 the number of 7-cyclic skeletons is 1. If n=7 the number of 7-cyclic skeletons is 9. If n=10 the number of 7-cyclic skeletons is 18436. - Parthasarathy Nambi, Jan 05 2007

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 7 on page 103.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs [gives different numbers for n > 10].

The analogs for n+k edges with k = -1, 0, ..., 7 are: A000602, A036671, A112410, A112619, A112408, A112424, A112425, this sequence, A112442. Cf. A121941.

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

New name, offset corrected, and a(11)-a(14) corrected by Andrey Zabolotskiy, Nov 24 2017

a(15)-a(21) added by Georg Grasegger, Jun 05 2023

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

Original entry on oeis.org

0, 0, 0, 1, 4, 18, 79, 326, 1278, 4875, 17978, 64720, 227842, 787546, 2678207, 8982754, 29761361, 97558039, 316778169, 1019996738, 3259673935, 10347077497, 32644696187, 102425388286, 319754805262

Offset: 1

Jonathan Vos Post, Dec 21 2005

nonn

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 3 on page 103.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs. [gives different a(18)]

The analogs for n+k edges with k = -1, 0, ..., 7 are: A000602, A036671, A112410, this sequence, A112408, A112424, A112425, A112426, A112442. Cf. A121941.

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

Corrected offset and new name from Andrey Zabolotskiy, Nov 24 2017

a(18) corrected and a(19)-a(25) added by Georg Grasegger, Jun 05 2023

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 2, 35, 707, 11477, 146428, 1530906, 13663758, 107554370, 764873164, 5004170844, 30537798974, 175688807383, 960958921848, 5030916734826

Offset: 1

Jonathan Vos Post, Dec 21 2005

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 8 on page 103.
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs [gives different a(11)].

The analogs for n+k edges with k = -1, 0, ..., 6 are: A000602, A036671, A112410, A112619, A112408, A112424, A112425, A112426. Cf. A121941.

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

New name, offset corrected, a(11) corrected, and a(14) added by Andrey Zabolotskiy, Nov 24 2017

a(15)-a(20) added by Georg Grasegger, Jun 05 2023

A125064 Number of simple graphs on at most 16 unlabeled vertices with maximal degree at most 4 with a single cycle of length 16-n.

Original entry on oeis.org

1, 2, 11, 39, 169, 534, 1612, 3894, 8771, 16307, 29391, 43291, 69429, 83571

Offset: 0

Parthasarathy Nambi, Jan 05 2007

In the terms of the paper by Hendrickson and Parks, a(n) is the number of monocyclic skeletons with up to 16 nodes with a ring of size 16-n.

James B. Hendrickson and Camden A. Parks, Generation and Enumeration of Carbon Skeletons, J. Chem. Inf. Comput. Sci., 31 (1991), pp. 101-107. See Table VI on page 103.

Cf. A000602, A036671, A112410, A112619, A112408, A112424, A112425, A112426.

Sum_n a(n) = Sum_{k=3..16} A036671(k).

Edited by Andrey Zabolotskiy, Feb 02 2025

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

A305059 Triangle read by rows: T(n,k) is the number of connected unicyclic graphs on n unlabeled nodes with cycle length k and all nodes having degree at most 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

nauty

Extensions

A125064 Number of simple graphs on at most 16 unlabeled vertices with maximal degree at most 4 with a single cycle of length 16-n.