cp's OEIS Frontend

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.

%I A000109 M1469 N0580 #136 Sep 02 2025 11:58:21
%S A000109 1,1,1,2,5,14,50,233,1249,7595,49566,339722,2406841,17490241,
%T A000109 129664753,977526957,7475907149,57896349553,453382272049,
%U A000109 3585853662949,28615703421545
%N 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.
%C A000109 Every planar triangulation on n >= 4 vertices is 3-connected (the connectivity either 3, 4, or 5) and its dual graph is a 3-connected cubic planar graph on 2n-4 vertices. - _Manfred Scheucher_, Mar 17 2023
%D A000109 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.]
%D A000109 M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties. Tech. Rep. 92-91, Info. and Comp. Sci. Dept., Univ. Calif. Irvine, 1992.
%D A000109 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.
%D A000109 B. Grünbaum, Convex Polytopes. Wiley, NY, 1967, p. 424.
%D A000109 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000109 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000109 David Wasserman, <a href="/A000109/b000109.txt">Table of n, a(n) for n = 3..23</a>
%H A000109 J. Bokowski and P. Schuchert, <a href="https://gdz.sub.uni-goettingen.de/id/PPN362609810_0013">Equifacetted 3-spheres as topes of nonpolytopal matroid polytopes</a>, Discrete Comput. Geom. 13 (1995), no. 3-4, 347-361.
%H A000109 R. Bowen and S. Fisk, <a href="/A000103/a000103.pdf">Generation of triangulations of the sphere</a> [Annotated scanned copy]
%H A000109 R. Bowen and S. Fisk, <a href="http://dx.doi.org/10.1090/S0025-5718-1967-0223277-3">Generation of triangulations of the sphere</a>, Math. Comp., 21 (1967), 250-252.
%H A000109 Gunnar Brinkmann and Brendan McKay, <a href="http://users.cecs.anu.edu.au/~bdm/plantri/">plantri and fullgen</a> programs for generation of certain types of planar graph.
%H A000109 Gunnar Brinkmann and Brendan McKay, <a href="/A000103/a000103_1.pdf">plantri and fullgen</a> programs for generation of certain types of planar graph [Cached copy, pdf file only, no active links, with permission]
%H A000109 CombOS - Combinatorial Object Server, <a href="http://combos.org/plantri">generate planar graphs</a>
%H A000109 Aharon Davidson, <a href="https://arxiv.org/abs/1907.03090">From Planck Area to Graph Theory: Topologically Distinct Black Hole Microstates</a>, arXiv:1907.03090 [gr-qc], 2019.
%H A000109 M. Deza, M. Dutour and P. W. Fowler, <a href="http://dx.doi.org/10.1021/ci049955h">Zigzags, railroads and knots in fullerenes</a>, J. Chem. Inf. Comput. Sci., 44 (2004), 1282-1293.
%H A000109 C. F. Earl and L. J. March, <a href="/A005500/a005500_1.pdf">Architectural applications of graph theory</a>, pp. 327-355 of R. J. Wilson and L. W. Beineke, editors, Applications of Graph Theory. Academic Press, NY, 1979. (Annotated scanned copy)
%H A000109 P. J. Federico, <a href="http://dx.doi.org/10.1016/S0021-9800(69)80050-5">Enumeration of polyhedra: the number of 9-hedra</a>, J. Combin. Theory, 7 (1969), 155-161.
%H A000109 Firsching, Moritz <a href="https://doi.org/10.1007/s10107-017-1120-0">Realizability and inscribability for simplicial polytopes via nonlinear optimization</a>.  Math. Program. 166, No. 1-2 (A), 273-295 (2017). Table 1
%H A000109 Komei Fukuda, Hiroyuki Miyata, and Sonoko Moriyama, <a href="http://arxiv.org/abs/1204.0645">Complete Enumeration of Small Realizable Oriented Matroids</a>. 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
%H A000109 Jan Goedgebeur and Patric R. J. Ostergard, <a href="https://arxiv.org/abs/2105.01363">Switching 3-Edge-Colorings of Cubic Graphs</a>, arXiv:2105:01363 [math.CO], May 2021. See Table 4.
%H A000109 R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
%H A000109 Lee Zheng Han and Chia Vui Leong, <a href="http://archive.ymsc.tsinghua.edu.cn/pacm_download/232/8908-A5.The_Walk_of_Maximal_Planar_Graphs.pdf">The Walk of Maximal Planar Graphs</a>, 2018.
%H A000109 Jorik Jooken, <a href="https://arxiv.org/abs/2508.20825">Computer-assisted graph theory: a survey</a>, arXiv:2508.20825 [math.CO], 2025. See p. 5.
%H A000109 Paul Jungeblut, <a href="https://i11www.iti.kit.edu/_media/teaching/theses/ma-jungeblut-19.pdf">Edge Guarding Plane Graphs</a>, Master Thesis, Karlsruhe Institute of Technology (Germany, 2019).
%H A000109 J. Lederberg, <a href="/A000602/a000602_10.pdf">Dendral-64, II</a>, Report to NASA, Dec 1965 [Annotated scanned copy]
%H A000109 J. Lederberg, <a href="http://www.jstor.org/stable/2314879">Hamilton circuits of convex trivalent polyhedra (up to 18 vertices)</a>, Am. Math. Monthly, 74 (1967), 522-527.
%H A000109 J. Lederberg, <a href="/A000109/a000109.pdf">Hamilton circuits of convex trivalent polyhedra (up to 18 vertices)</a>, Am. Math. Monthly, 74 (1967), 522-527. (Annotated scanned copy)
%H A000109 F. H. Lutz, <a href="https://arxiv.org/abs/math/0506372">Triangulated manifolds with few vertices: Combinatorial Manifolds</a>, arXiv:math/0506372 [math.CO], 2005.
%H A000109 G. P. Michon, <a href="http://www.numericana.com/data/polyhedra.htm">Counting Polyhedra</a>
%H A000109 Manfred Scheucher, Hendrik Schrezenmaier, and Raphael Steiner, <a href="https://arxiv.org/abs/1811.06482">A Note On Universal Point Sets for Planar Graphs</a>, arXiv:1811.06482 [math.CO], 2018.
%H A000109 I. Sciriha and P. W. Fowler, <a href="https://dx.doi.org/10.1021/ci700097j">Nonbonding Orbitals in Fullerenes: Nuts and Cores in Singular Polyhedral Graphs</a>, J. Chem. Inf. Model., 47, 5, 1763 - 1775, 2007.
%H A000109 A. Stoimenow, <a href="https://doi.org/10.1007/s00493-014-2840-x">A theorem on graph embedding with a relation to hyperbolic volume</a>, Combinatorica, October 2016, Volume 36, Issue 5, pp 557-589.
%H A000109 Thom Sulanke, <a href="http://hep.physics.indiana.edu/~tsulanke/graphs/surftri/">Generating triangulations of surfaces (surftri)</a>, (also subpages).
%H A000109 William T. Tutte, <a href="https://doi.org/10.4153/CJM-1962-002-9">A census of planar triangulations</a>, Canad. J. Math. 14 (1962), 21-38.
%H A000109 William T. Tutte, <a href="https://doi.org/10.1016/0095-8956(80)90059-3">On the enumeration of convex polyhedra</a>, J. Combin. Theory Ser. B 28 (1980), 105-126.
%H A000109 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CubicPolyhedralGraph.html">Cubic Polyhedral Graph</a>
%H A000109 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SimplePolyhedron.html">Simple Polyhedron</a>
%H A000109 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TriangulatedGraph.html">Triangulated Graph</a>
%H A000109 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000109 From _William P. Orrick_, Apr 07 2021: (Start)
%F A000109 a(n) >= A007816(n-3)/n! = binomial(n,2)*(4*n-11)!/(n!*(3*n-6)!) for all n >= 4.
%F A000109 a(n) ~ A007816(n-3)/n! = binomial(n,2)*(4*n-11)!/(n!*(3*n-6)!) ~ (1/64)*sqrt(1/(6*Pi))*n^(-7/2)*(256/27)^(n-2), using the theorem that the automorphism group of a maximal planar graph is almost certainly trivial as n gets large. (Tutte)
%F A000109 (End)
%Y A000109 Cf. A005964, A007816, A058378, A253882.
%Y A000109 Cf. A000944, A007021, A111358.
%K A000109 nonn,nice,hard,more,core,changed
%O A000109 3,4
%A A000109 _N. J. A. Sloane_
%E A000109 Extended by _Brendan McKay_ and _Gunnar Brinkmann_ using their program "plantri", Dec 19 2000
%E A000109 Definition clarified by _Manfred Scheucher_, Mar 17 2023