The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002851 Number of unlabeled trivalent (or cubic) connected graphs with 2n nodes.
(Formerly M1521 N0595)

%I M1521 N0595

%S 1,0,1,2,5,19,85,509,4060,41301,510489,7319447,117940535,2094480864,

%T 40497138011,845480228069,18941522184590,453090162062723,

%U 11523392072541432,310467244165539782,8832736318937756165

%N Number of unlabeled trivalent (or cubic) connected graphs with 2n nodes.

%D CRC Handbook of Combinatorial Designs, 1996, p. 647.

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 195.

%D 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.

%D 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.

%D R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence)

%H G. Brinkmann, J. Goedgebeur and B. D. McKay, <a href="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/1801">Generation of cubic graphs</a>, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80

%H G. Brinkmann, J. Goedgebeur, N. Van Cleemput, <a href="http://caagt.ugent.be/jgoedgeb/paper-cubic_graphs_survey.pdf">The history of the generation of cubic graphs</a>, Int. J. Chem. Modeling 5 (2-3) (2013) 67-89

%H F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, <a href="http://alexandria.tue.nl/repository/books/252909.pdf">Computer investigations of cubic graphs</a>, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.

%H F. C. Bussemaker, S. Cobeljic, D. M. Cvetkovic, J. J. Seidel, <a href="http://dx.doi.org/10.1016/0095-8956(77)90034-X">Cubic graphs on <= 14 vertices</a> J. Combinatorial Theory Ser. B 23(1977), no. 2-3, 234--235. MR0485524 (58 #5354).

%H Timothy B. P. Clark, Adrian Del Maestro, <a href="http://arxiv.org/abs/1506.02048">Moments of the inverse participation ratio for the Laplacian on finite regular graphs</a>, arXiv:1506.02048 [math-ph], 2015.

%H H. Gropp, <a href="http://dx.doi.org/10.1016/0012-365X(92)90592-4">Enumeration of regular graphs 100 years ago</a>, Discrete Math., 101 (1992), 73-85.

%H House of Graphs, <a href="http://hog.grinvin.org/Cubic">Cubic graphs</a>

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/C_k-reg_girth_ge_g_index">Index of sequences counting connected k-regular simple graphs with girth at least g</a>

%H M. Klin, M. Rücker, Ch. Rücker and G. Tinhofer, <a href="http://www-lit.ma.tum.de/veroeff/html/950.05003.html">Algebraic Combinatorics</a> [broken link]

%H M. Klin, M. Rücker, Ch. Rücker, G. Tinhofer, <a href="ftp://ftp.mathe2.uni-bayreuth.de/axel/papers/klin:algebraic_combinatorics_in_mathematical_chemistry_methods_and_applications_1_permutation_groups_and_coherent_algebras.ps.gz">Algebraic Combinatorics</a> (1997)

%H Denis S. Krotov, Konstantin V. Vorob'ev, <a href="https://arxiv.org/abs/1812.02166">On unbalanced Boolean functions attaining the bound 2n/3-1 on the correlation immunity</a>, arXiv:1812.02166 [math.CO], 2018.

%H R. J. Mathar/Wikipedia, <a href="http://en.wikipedia.org/wiki/Table_of_simple_cubic_graphs">Table of simple cubic graphs</a> [From _N. J. A. Sloane_, Feb 28 2012]

%H M. Meringer, <a href="http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html">Tables of Regular Graphs</a>

%H R. W. Robinson and N. C. Wormald, <a href="http://dx.doi.org/10.1002/jgt.3190070412">Numbers of cubic graphs</a>. J. Graph Theory 7 (1983), no. 4, 463-467.

%H Sage, <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html">Common Graphs (Graph Generators)</a>

%H J. J. Seidel, R. R. Korfhage, & N. J. A. Sloane, <a href="/A002851/a002851.pdf">Correspondence 1975</a>

%H H. M. Sultan, <a href="http://www.math.columbia.edu/~hsultan/papers/separatingpantscomplex_v3.pdf">Separating pants decompositions in the pants complex</a>.

%H H. M. Sultan, <a href="http://arxiv.org/abs/1106.1472">Net of Pants Decompositions Containing a non-trivial Separating Curve in the Pants Complex</a>, arXiv:1106.1472 [math.GT], 2011.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CubicGraph.html">Cubic Graph</a>

%e 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 + ...

%e a(0) = 1 because the null graph (with no vertices) is vacuously 3-regular.

%e a(1) = 0 because there are no simple connected cubic graphs with 2 nodes.

%e a(2) = 1 because the tetrahedron is the only cubic graph with 4 nodes.

%Y Cf. A004109 (labeled connected cubic), A321304 (rooted connected cubic), A321305 (signed connected cubic), A000421 (connected cubic multigraphs), A275744 (multisets).

%Y Contribution (almost all) from _Jason Kimberley_, Feb 10 2011: (Start)

%Y 3-regular simple graphs: this sequence (connected), A165653 (disconnected), A005638 (not necessarily connected), A005964 (planar).

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

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

%Y 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)

%K nonn,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from R. C. Read (rcread(AT)math.uwaterloo.ca)

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 16 05:20 EDT 2021. Contains 343030 sequences. (Running on oeis4.)