Counting 5-connected planar triangulations
A rooted map on the sphere is \(M\)-type if it contains neither loops nor multiple edges, and if all interior faces have degrees 3 or 4. Defining \(m_{a,b,c}\) to be the number of \(M\)-type maps with \(a\) interior triangular faces, \(b\) interior quadrangular faces, and a root face of degree \(c\), the authors determine an equation satisfied by the generating function \(M(x,y,z)=\sum m_{a,b,c}x^ay^bz^c\). The equation involves generating functions \(M_3(x,y)\) and \(M_4(x,y)\), which respectively enumerate \(M\)-type maps with a triangular and a quadrangular root face. The presence of \(M_3\) and \(M_4\) in the equation prevents solution of the equation by ``the standard quadratic method. Instead, the authors apply a technique introduced by \textit{E. A. Bender} and \textit{E. R. Canfield} [The number of degree-restricted rooted maps on the sphere. SIAM J. Discrete Math. 7, No. 1, 9-15 (1994; Zbl 0794.05048)], based on a theorem of the reviewer [Math. Ann. 158, 82-89 (1965; Zbl 0136.02503), Math. Ann. 170, 327-333 (1967; Zbl 0144.03502)] to ultimately determine the generating function for the number \(t_n\) of rooted 5-connected planar triangulations with \(2n\) faces. It is shown in Theorem 2 that NEWLINE\[NEWLINEt_n=\frac{3c_3}{4\sqrt\pi}n^{-\frac 52}w_0^{-n}\left(1+O\left(\frac 1n\right) \right) \quad \text{as}\quad n\to\infty,NEWLINE\]NEWLINE where \(w_0\approx 0.24775354\) and \(c_3\approx 0.00067543010\). They apply a result of L. B. Richmond and the third author [cf. \textit{L. B. Richmond} and \textit{N. C. Wormald}, Almost all maps are asymmetric. J. Comb. Theory, Ser. B 63, No. 1, 1-7 (1995; Zbl 0820.05017)] to prove that the number of unrooted 5-connected planar triangulations with \(2n\) faces is asymptotic to \(\frac{c_3}{16\sqrt\pi}n^{-\frac 72}w_0^{-n}\) as \(n\to\infty\), for the same constants \(c_3\) and \(w_0\).
- 2-Isomorphic Graphs
- A Census of Planar Maps
- A Census of Planar Triangulations
- Almost all maps are asymmetric
- Asymptotic Methods in Enumeration
- Enumeration of Labelled Graphs I: 3-Connected Graphs
- Enumeration of Quadrangular Dissections of the Disk
- Enumeration of Triangulations of the Disk
- scientific article; zbMATH DE number 3724488 (Why is no real title available?)
- On Counting Rooted Triangular Maps
- On the existence of square roots in certain rings of power series
- Remarks on an asymptotic method in combinatorics
- The enumeration of c-nets via quadrangulations
- The Number of Degree-Restricted Rooted Maps on the Sphere
- The number of rooted triangular maps on a surface
- Face sizes of 3-polytopes
- The asymptotic behaviour of the number of three-connected triangulations of the disk, with a reflective symmetry in a line
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Construction of planar triangulations with minimum degree 5
- scientific article; zbMATH DE number 5017751 (Why is no real title available?)
- scientific article; zbMATH DE number 1894723 (Why is no real title available?)
- A Schnyder-type drawing algorithm for 5-connected triangulations
- On triangulations with high vertex degree
This page was built for publication: Counting 5-connected planar triangulations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746482)
