A005967 -id:A005967 - cp's OEIS frontend

A002851 Number of unlabeled trivalent (or cubic) connected simple graphs with 2n nodes.

1, 0, 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447, 117940535, 2094480864, 40497138011, 845480228069, 18941522184590, 453090162062723, 11523392072541432, 310467244165539782, 8832736318937756165

Offset: 0

N. J. A. Sloane

			G.f. = 1 + x^2 + 2*x^3 + 5*x^4 + 19*x^5 + 85*x^6 + 509*x^7 + 4060*x^8 + 41302*x^9 + 510489*x^10 + 7319447*x^11 + ...
a(0) = 1 because the null graph (with no vertices) is vacuously 3-regular.
a(1) = 0 because there are no simple connected cubic graphs with 2 nodes.
a(2) = 1 because the tetrahedron is the only cubic graph with 4 nodes.
a(3) = 2 because there are two simple cubic graphs with 6 nodes: the bipartite graph K_{3,3} and the triangular prism graph.

CRC Handbook of Combinatorial Designs, 1996, p. 647.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 195.
R. C. Read, Some applications of computers in graph theory, in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978, pp. 417-444.
R. C. Read and G. F. Royle, Chromatic roots of families of graphs, pp. 1009-1029 of Y. Alavi et al., eds., Graph Theory, Combinatorics and Applications. Wiley, NY, 2 vols., 1991.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence)

Peter Adams, Ryan C. Bunge, Roger B. Eggleton, Saad I. El-Zanati, Uğur Odabaşi, and Wannasiri Wannasit, Decompositions of complete graphs and complete bipartite graphs into bipartite cubic graphs of order at most 12, Bull. Inst. Combinatorics and Applications (2021) Vol. 92, 50-61.
G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80
G. Brinkmann, J. Goedgebeur, and N. Van Cleemput, The history of the generation of cubic graphs, Int. J. Chem. Modeling 5 (2-3) (2013) 67-89
F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, Computer investigations of cubic graphs, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.
F. C. Bussemaker, S. Cobeljic, D. M. Cvetkovic, and J. J. Seidel, Cubic graphs on <= 14 vertices J. Combinatorial Theory Ser. B 23(1977), no. 2-3, 234--235. MR0485524 (58 #5354).
Timothy B. P. Clark and Adrian Del Maestro, Moments of the inverse participation ratio for the Laplacian on finite regular graphs, arXiv:1506.02048 [math-ph], 2015.
Jan Goedgebeur and Patric R. J. Ostergard, Switching 3-Edge-Colorings of Cubic Graphs, arXiv:2105:01363 [math.CO], May 2021. See Table 1.
H. Gropp, Enumeration of regular graphs 100 years ago, Discrete Math., 101 (1992), 73-85.
House of Graphs, Cubic graphs
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g
M. Klin, M. Rücker, Ch. Rücker and G. Tinhofer, Algebraic Combinatorics [broken link]
M. Klin, M. Rücker, Ch. Rücker, and G. Tinhofer, Algebraic Combinatorics (1997)
Denis S. Krotov and Konstantin V. Vorob'ev, On unbalanced Boolean functions attaining the bound 2n/3-1 on the correlation immunity, arXiv:1812.02166 [math.CO], 2018.
R. J. Mathar/Wikipedia, Table of simple cubic graphs [From _N. J. A. Sloane_, Feb 28 2012]
M. Meringer, Tables of Regular Graphs
R. W. Robinson and N. C. Wormald, Numbers of cubic graphs. J. Graph Theory 7 (1983), no. 4, 463-467.
Sage, Common Graphs (Graph Generators)
J. J. Seidel, R. R. Korfhage, & N. J. A. Sloane, Correspondence 1975
H. M. Sultan, Separating pants decompositions in the pants complex.
H. M. Sultan, Net of Pants Decompositions Containing a non-trivial Separating Curve in the Pants Complex, arXiv:1106.1472 [math.GT], 2011.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Cubic Graph

Cf. A004109 (labeled connected cubic), A361407 (rooted connected cubic), A321305 (signed connected cubic), A000421 (connected cubic loopless multigraphs), A005967 (connected cubic multigraphs), A275744 (multisets).
Contribution (almost all) from Jason Kimberley, Feb 10 2011: (Start)
3-regular simple graphs: this sequence (connected), A165653 (disconnected), A005638 (not necessarily connected), A005964 (planar).
Connected regular graphs A005177 (any degree), A068934 (triangular array), specified degree k: this sequence (k=3), A006820 (k=4), A006821 (k=5), A006822 (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).
Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: this sequence (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).
Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

More terms from Ronald C. Read

A000421 Number of isomorphism classes of connected 3-regular (trivalent, cubic) loopless multigraphs of order 2n.

Original entry on oeis.org

1, 2, 6, 20, 91, 509, 3608, 31856, 340416, 4269971, 61133757, 978098997, 17228295555, 330552900516, 6853905618223, 152626436936272, 3631575281503404, 91928898608055819, 2466448432564961852, 69907637101781318907

Offset: 1

N. J. A. Sloane

a(n) is also the number of isomorphism classes of connected 3-regular simple graphs of order 2n with possibly loops. - Nico Van Cleemput, Jun 04 2014

There are no graphs of order 2n+1 satisfying the condition above. - Natan Arie Consigli, Dec 20 2019

			From _Natan Arie Consigli_, Dec 20 2019: (Start)
a(1) = 1: with two nodes the only viable option is the triple edged path multigraph.
a(2) = 4: with four nodes we have two cases: the tetrahedral graph and the square graph with single and double edges on opposite sides.
(End)

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 92 [gives incorrect a(6)].
CRC Handbook of Combinatorial Designs, 1996, p. 651 [or: 2006, table 4.40].

Jan-Peter Börnsen, Anton E. M. van de Ven, Tangent Developable Orbit Space of an Octupole, arXiv:1807.04817 [hep-th], 2018.
G. Brinkmann, N. Van Cleemput, T. Pisanski, Generation of various classes of trivalent graphs, Theoretical Computer Science 502, 2013, pp.16-29.
R. J. Mathar, Cubic multigraphs A000421
Brendan McKay and others, Nauty Traces

Column k=3 of A328682 (table of k-regular n-node multigraphs).

Cf. A129416, A005967 (loops allowed), A129417, A129419, A129421, A129423, A129425, A002851 (no multiedges).

for n in {1..10}; do geng -cqD3 $[2*$n] | multig -ur3; done # Sean A. Irvine, Sep 24 2015

Inverse Euler transform of A129416. - Andrew Howroyd, Mar 19 2020

More terms from Brendan McKay, Apr 15 2007

a(13)-a(20) from Andrew Howroyd, Mar 19 2020

A129427 Number of isomorphism classes of 3-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

1, 2, 8, 31, 140, 722, 4439, 32654, 289519, 3054067, 37584620, 527968286, 8308434931, 144345554051, 2738280739075, 56245013793246, 1242596591479816, 29366532494796900, 739033832149588904, 19726887762569763453

Offset: 0

Brendan McKay, Apr 15 2007

nonn

a(1)..a(11) computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

P. A. Morris, Letter to N. J. A. Sloane, Mar 02 1971.

R. de Mello Koch, S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
P. A. Morris, Letter to N. J. A. Sloane, Mar 02 1971.
R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436. - _Jason Kimberley_, Sep 17 2009

Column k=3 of A167625.

Cf. A005967 (connected, inv. Euler trans.), A129416, A129429, A129431, A129433, A129435, A129437, A005638.

h = SymmetricFunctions(QQ).homogeneous()
def A129427(n):
    X = h([2*n]).plethysm(h([3]))
    Y = h([3*n]).plethysm(h([2]))
    return X.scalar(Y)
# Bruce Westbury, Aug 16 2013

a(n)=N\{S_{2n}[S_3] * S_{3n}[S_2]\}. - Jason Kimberley, Sep 17 2009

Using equation (5.8) of Read 1959, new terms a(12) and a(13) were computed in MAGMA by Jason Kimberley, Sep 17 2009
Further terms a(14)-a(16) also computed by Jason Kimberley, announced Nov 09 2009
Formula corrected from n vertices to 2n vertices by Jason Kimberley, Nov 09 2009
Added a(0). - N. J. A. Sloane, Aug 26 2013
a(17)-a(19) from Sean A. Irvine, Oct 29 2016

A085549 Number of isomorphism classes of connected 4-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 2, 4, 10, 28, 97, 359, 1635, 8296, 48432, 316520, 2305104, 18428254, 160384348, 1506613063, 15180782537, 163211097958, 1864251304892, 22540603640086, 287577260214946, 3860595341568062, 54397355465967057, 802684717378090204

Offset: 1

Benjamin A. Burton (bab(AT)debian.org), Jul 04 2003

Also the number of different potential face pairing graphs for closed 3-manifold triangulations.

Computed from A129429 by an inverse Euler transform. - R. J. Mathar, Mar 09 2019

B. A. Burton, Minimal triangulations and face pairing graphs, preprint, 2003.

Andrew Howroyd, Table of n, a(n) for n = 1..40
B. A. Burton, Regina (3-manifold topology software).
B. A. Burton, Minimal triangulations and normal surfaces, Ph.D. thesis, University of Melbourne, 2003.
B. A. Burton, Face pairing graphs and 3-manifold enumeration, arXiv:math/0307382 [math.GT], 2003.
B. A. Burton, Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find, Discrete and Computational Geometry, 38 (2007), 527-571.
R. de Mello Koch, S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
H. Kleinert, A. Pelster, B. Kastening, M. Bachmann, Recursive graphical construction of Feynman diagrams and their multiplicities in Phi^4 and Phi^2*A theory, Phys. Rev. E 62 (2) (2000), 1537 eq (4.20) or arXiv:hep-th/9907168, 1999.
B. Martelli and C. Petronio, Three-manifolds having complexity at most 9, Experiment. Math., Vol. 10 (2001), pp. 207-236
R. J. Mathar, Illustrations

Column k=4 of A333397.

Cf. A129429, A129417, A005967, A129430, A129432, A129434, A129436, A118560.

A129429 = Cases[Import["https://oeis.org/A129429/b129429.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A129429] (* Jean-François Alcover, Dec 03 2019, updated Mar 17 2020 *)

Inverse Euler transform of A129429.

a(12)-a(16) from Brendan McKay, Apr 15 2007, computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/
Edited by N. J. A. Sloane, Oct 01 2007
a(17)-a(23) from A129429 from Jean-François Alcover, Dec 03 2019

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

3, 26, 639, 40264, 5846105, 1620621150, 752480161278, 538934691750368, 562620407713724992, 820458681175954269942, 1616087981640640784235446, 4183688192689449962777539596, 13914233045360143936837907106395, 58319096569220501055727735345999221

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=5 of A333397.

Cf. A129431, A129419, A005967, A085549, A129432, A129434, A129436.

Inverse Euler transform of A129431. - Andrew Howroyd, Mar 19 2020

a(8)-a(14) added by Andrew Howroyd, Mar 21 2020

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1, 1, 3, 4, 5, 1, 0, 0, 1, 0, 3, 0, 10, 0, 1, 0, 0, 1, 1, 4, 9, 26, 28, 17, 1, 0, 0, 1, 0, 4, 0, 47, 0, 97, 0, 1, 0, 0, 1, 1, 5, 17, 91, 291, 639, 359, 71, 1, 0, 0, 1, 0, 5, 0, 149, 0, 2789, 0, 1635, 0, 1, 0, 0

Offset: 0

Andrew Howroyd, Mar 18 2020

This sequence can be derived from A167625 by inverse Euler transform.

			Array begins:
=========================================================
n\k | 0 1 2  3    4     5        6       7          8
----+----------------------------------------------------
  0 | 1 1 1  1    1     1        1       1          1 ...
  1 | 1 0 1  0    1     0        1       0          1 ...
  2 | 0 1 1  2    2     3        3       4          4 ...
  3 | 0 0 1  0    4     0        9       0         17 ...
  4 | 0 0 1  5   10    26       47      91        149 ...
  5 | 0 0 1  0   28     0      291       0       1934 ...
  6 | 0 0 1 17   97   639     2789   12398      44821 ...
  7 | 0 0 1  0  359     0    35646       0    1631629 ...
  8 | 0 0 1 71 1635 40264   622457 8530044   89057367 ...
  9 | 0 0 1  0 8296     0 14019433       0 6849428873 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..405 (first 28 antidiagonals)

Columns k=3..8 (with interspersed 0's for odd k) are: A005967, A085549, A129430, A129432, A129434, A129436.

Cf. A167625 (not necessarily connected), A322115 (not necessarily regular), A328682 (loopless), A333330.

Column k is the inverse Euler transform of column k of A167625.

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 9, 47, 291, 2789, 35646, 622457, 14019433, 395208047, 13561118011, 555498075986, 26751985389463, 1496090275853092, 96154662330195078, 7038800665162854369, 582281978355495520076, 54057819690711609171892, 5597375885970846586170796, 642829784413912305507730345

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=6 of A333397.

Cf. A129433, A129421, A005967, A085549, A129430, A129434, A129436.

Inverse Euler transform of A129433. - Andrew Howroyd, Mar 19 2020

a(13)-a(20) added by Andrew Howroyd, Mar 19 2020

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

4, 91, 12398, 8530044, 20068725095, 122563246940846, 1657847267734501346, 44557979504639651662163, 2193071655191529316254072193, 185380797361862371952777763438426

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=7 of A333397.

Cf. A129435, A129423, A005967, A085549, A129430, A129432, A129436.

Inverse Euler transform of A129435. - Andrew Howroyd, Mar 19 2020

a(6)-a(10) added by Andrew Howroyd, Mar 21 2020

A129436 Number of isomorphism classes of connected 8-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 4, 17, 149, 1934, 44821, 1631629, 89057367, 6849428873, 713780361312, 97876276145119, 17259548258350637, 3840154740252625874, 1060662127742505706789, 358584059544008234423217, 146560585570176100774010071, 71630591614693085251230481320, 41456445821273701849195905028292

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=8 of A333397.

Cf. A129437, A129425, A005967, A085549, A129430, A129432, A129434.

Inverse Euler transform of A129437. - Andrew Howroyd, Mar 19 2020

a(11)-a(18) added by Andrew Howroyd, Mar 21 2020

A361447 Number of connected 3-regular (cubic) multigraphs on 2n unlabeled nodes rooted at an unoriented edge (or loop) whose removal does not disconnect the graph, loops allowed.

Original entry on oeis.org

1, 2, 9, 49, 338, 2744, 26025, 282419, 3463502, 47439030, 718618117, 11937743088, 215896959624, 4224096594516, 88919920910684, 2004237153640098, 48165411560792500, 1229462431057436457, 33221743136066636436, 947415638925100675208, 28436953641282225835143

Offset: 0

Andrew Howroyd, Mar 12 2023

nonn

a(0) = 1 by convention. Loops add two to the degree of a node.
Instead of a rooted edge, the graph can be considered to have a pair of external legs (or half-edges). The external legs add 1 to the degree of a node, but do not contribute to the connectivity of the graph.
The 4-regular version of this sequence is A361135 since removing a single edge from a connected even degree regular graph cannot disconnect the graph.

			The illustrations in A352175 by _R. J. Mathar_ show 1, 2, 9, and 49 connected graphs corresponding to the initial terms of this sequence.

Cf. A005967 (unrooted), A129427, A352175, A361135, A361412, A361446, A361448.

G.f.: B(x) - x*(B(x)^2 + B(x^2))/2 where B(x) is the g.f. of A361412.

cp's OEIS Frontend

A002851 Number of unlabeled trivalent (or cubic) connected simple graphs with 2n nodes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A000421 Number of isomorphism classes of connected 3-regular (trivalent, cubic) loopless multigraphs of order 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

nauty

Formula

Extensions

A129427 Number of isomorphism classes of 3-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Sage

Formula

Extensions

A085549 Number of isomorphism classes of connected 4-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions