login
Numbers of planar triangulations with minimum degree 5 and without separating 3- or 4-cycles - that is 3- or 4-cycles where the interior and exterior contain at least one vertex.
4

%I #26 Mar 17 2023 06:51:43

%S 1,0,1,1,3,4,12,23,71,187,627,1970,6833,23384,82625,292164,1045329,

%T 3750277,13532724,48977625,177919099,648145255,2368046117,8674199554,

%U 31854078139,117252592450,432576302286,1599320144703,5925181102878

%N Numbers of planar triangulations with minimum degree 5 and without separating 3- or 4-cycles - that is 3- or 4-cycles where the interior and exterior contain at least one vertex.

%C A006791 and this sequence are the same sequence. The correspondence is just that these objects are planar duals of each other. But the offset and step are different: if the cubic graph has 2*n vertices, the dual triangulation has n+2 vertices. - _Brendan McKay_, May 24 2017

%C Also the number of 5-connected triangulations on n vertices. - _Manfred Scheucher_, Mar 17 2023

%H G. Brinkmann, <a href="http://www.mathematik.uni-bielefeld.de/~CaGe/">CaGe</a>.

%H 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 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 G. Brinkmann and Brendan D. McKay, <a href="http://dx.doi.org/10.1016/j.disc.2005.06.019">Construction of planar triangulations with minimum degree 5 </a>, Disc. Math. vol 301, iss. 2-3 (2005) 147-163.

%H D. A. Holton and B. D. McKay, <a href="http://dx.doi.org/10.1016/0095-8956(88)90075-5">The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices</a>, J. Combinat. Theory B vol 45, iss. 3 (1988) 305-319.

%H D. A. Holton and B. D. McKay, <a href="http://dx.doi.org/10.1016/0095-8956(89)90025-7">Erratum</a>, J. Combinat. Theory B vol 47, iss. 2 (1989) 248.

%e The icosahedron is the smallest triangulation with minimum degree 5 and it doesn't contain any separating 3- or 4-cycles. Examples can easily be seen as 2D and 3D pictures using the program CaGe cited above.

%Y Cf. A081621, A007894, A006791, A000109, A007021, A361578.

%K nonn

%O 12,5

%A _Gunnar Brinkmann_, Nov 07 2005