A002851
Number of unlabeled trivalent (or cubic) connected simple graphs with 2n nodes.
Original entry on oeis.org
1, 0, 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447, 117940535, 2094480864, 40497138011, 845480228069, 18941522184590, 453090162062723, 11523392072541432, 310467244165539782, 8832736318937756165
Offset: 0
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).
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).
More terms from Ronald C. Read
A000109
Number of simplicial polyhedra with n vertices; simple planar graphs with n vertices and 3n-6 edges; maximal simple planar graphs with n vertices; planar triangulations with n vertices; triangulations of the sphere with n vertices; 3-connected cubic planar graphs on 2n-4 vertices.
Original entry on oeis.org
1, 1, 1, 2, 5, 14, 50, 233, 1249, 7595, 49566, 339722, 2406841, 17490241, 129664753, 977526957, 7475907149, 57896349553, 453382272049, 3585853662949, 28615703421545
Offset: 3
- G. Brinkmann and Brendan McKay, in preparation. [Looking at http://users.cecs.anu.edu.au/~bdm/publications.html, there are a few papers with Brinkmann that seem relevant, in particular #126 but also #97, 81, 158. Perhaps the right one is 126.]
- M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties. Tech. Rep. 92-91, Info. and Comp. Sci. Dept., Univ. Calif. Irvine, 1992.
- C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979.
- B. Grünbaum, Convex Polytopes. Wiley, NY, 1967, p. 424.
- 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).
- David Wasserman, Table of n, a(n) for n = 3..23
- J. Bokowski and P. Schuchert, Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes, Discrete Comput. Geom. 13 (1995), no. 3-4, 347-361.
- R. Bowen and S. Fisk, Generation of triangulations of the sphere [Annotated scanned copy]
- R. Bowen and S. Fisk, Generation of triangulations of the sphere, Math. Comp., 21 (1967), 250-252.
- Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph.
- Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph [Cached copy, pdf file only, no active links, with permission]
- CombOS - Combinatorial Object Server, generate planar graphs
- Aharon Davidson, From Planck Area to Graph Theory: Topologically Distinct Black Hole Microstates, arXiv:1907.03090 [gr-qc], 2019.
- M. Deza, M. Dutour and P. W. Fowler, Zigzags, railroads and knots in fullerenes, J. Chem. Inf. Comput. Sci., 44 (2004), 1282-1293.
- C. F. Earl and L. J. March, Architectural applications of graph theory, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
- P. J. Federico, Enumeration of polyhedra: the number of 9-hedra, J. Combin. Theory, 7 (1969), 155-161.
- Firsching, Moritz Realizability and inscribability for simplicial polytopes via nonlinear optimization. Math. Program. 166, No. 1-2 (A), 273-295 (2017). Table 1
- Komei Fukuda, Hiroyuki Miyata, and Sonoko Moriyama, Complete Enumeration of Small Realizable Oriented Matroids. Discrete Comput. Geom. 49 (2013), no. 2, 359--381. MR3017917. Also arXiv:1204.0645 [math.CO], 2012. - From _N. J. A. Sloane_, Feb 16 2013
- Jan Goedgebeur and Patric R. J. Ostergard, Switching 3-Edge-Colorings of Cubic Graphs, arXiv:2105:01363 [math.CO], May 2021. See Table 4.
- R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
- Lee Zheng Han and Chia Vui Leong, The Walk of Maximal Planar Graphs, 2018.
- Jorik Jooken, Computer-assisted graph theory: a survey, arXiv:2508.20825 [math.CO], 2025. See p. 5.
- Paul Jungeblut, Edge Guarding Plane Graphs, Master Thesis, Karlsruhe Institute of Technology (Germany, 2019).
- J. Lederberg, Dendral-64, II, Report to NASA, Dec 1965 [Annotated scanned copy]
- J. Lederberg, Hamilton circuits of convex trivalent polyhedra (up to 18 vertices), Am. Math. Monthly, 74 (1967), 522-527.
- J. Lederberg, Hamilton circuits of convex trivalent polyhedra (up to 18 vertices), Am. Math. Monthly, 74 (1967), 522-527. (Annotated scanned copy)
- F. H. Lutz, Triangulated manifolds with few vertices: Combinatorial Manifolds, arXiv:math/0506372 [math.CO], 2005.
- G. P. Michon, Counting Polyhedra
- Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner, A Note On Universal Point Sets for Planar Graphs, arXiv:1811.06482 [math.CO], 2018.
- I. Sciriha and P. W. Fowler, Nonbonding Orbitals in Fullerenes: Nuts and Cores in Singular Polyhedral Graphs, J. Chem. Inf. Model., 47, 5, 1763 - 1775, 2007.
- A. Stoimenow, A theorem on graph embedding with a relation to hyperbolic volume, Combinatorica, October 2016, Volume 36, Issue 5, pp 557-589.
- Thom Sulanke, Generating triangulations of surfaces (surftri), (also subpages).
- William T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962), 21-38.
- William T. Tutte, On the enumeration of convex polyhedra, J. Combin. Theory Ser. B 28 (1980), 105-126.
- Eric Weisstein's World of Mathematics, Cubic Polyhedral Graph
- Eric Weisstein's World of Mathematics, Simple Polyhedron
- Eric Weisstein's World of Mathematics, Triangulated Graph
- Index entries for "core" sequences
A072552
Number of connected planar regular graphs of degree 4 with n nodes.
Original entry on oeis.org
1, 0, 1, 1, 3, 3, 13, 21, 68, 166, 543, 1605, 5413, 17735, 61084, 210221, 736287
Offset: 6
Markus Meringer (meringer(AT)uni-bayreuth.de), Aug 05 2002
From _Allan Bickle_, May 13 2024: (Start)
For n=6, the unique graph is the octahedron.
For n=8, the unique graph is the square of an 8-cycle.
For n=9, the unique graph is the dual of the Herschel graph. (End)
A058378
Number of trivalent 2-connected planar graphs with 2n nodes.
Original entry on oeis.org
0, 1, 1, 3, 8, 29, 114, 583, 3310, 21168, 144622, 1039495, 7731540
Offset: 1
- 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.
- Computed by Brendan McKay and Gunnar Brinkmann using their program "plantri", Dec 19 2000.
A101204
Triangle read by rows: T(n,k) = number of planar trivalent (or cubic) loopless multigraphs with 2n nodes and exactly k double bonds, for 0 <= k <= n.
Original entry on oeis.org
1, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 4, 5, 4, 1, 9, 16, 22, 16, 7, 1, 32, 75, 112, 86, 41, 10, 1, 133
Offset: 0
Triangle begins
1,
0, 1,
1, 0, 1,
1, 1, 2, 1,
3, 4, 5, 4, 1
9, 16, 22, 16, 7, 1
32, 75, 112, 86, 41, 10, 1
133, ...
- 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.
Row sums give
A005966. First column is
A005964 (trivalent connected planar graphs with 2n nodes). Second and third columns give
A101205,
A101206.
A204186
Number of trivalent connected (or cubic) graphs with 2n nodes that are not planar.
Original entry on oeis.org
0, 0, 1, 2, 10, 53, 376, 3379, 37408, 485680, 7150241, 116726073, 2085446355
Offset: 1
A358284
Number of connected planar cubic graphs with 2*n nodes and zero edge-Kempe equivalence classes.
Original entry on oeis.org
0, 0, 0, 1, 3, 19, 98, 583, 3641, 24584, 174967
Offset: 2
A358285
Number of connected planar cubic graphs with 2*n nodes and exactly one edge-Kempe equivalence class.
Original entry on oeis.org
1, 1, 1, 8, 28, 111, 556, 3108, 19368, 128811, 897475
Offset: 2
A358286
Number of connected planar cubic graphs with 2*n nodes and the maximum number of edge-Kempe equivalence classes.
Original entry on oeis.org
1, 1, 1, 8, 1, 3, 27, 1, 1, 1, 7, 42, 1, 2
Offset: 2
Showing 1-9 of 9 results.
Comments