A pattern for the asymptotic number of rooted maps on surfaces. (English) Zbl 0792.05073
Let \(T_ g(n)\) \((P_ g(n))\) be the number of \(n\)-edged rooted maps (in a certain class) on an orientable (non-orientable) surface of type \(g\), and let \(t_ g\) and \(p_ g\) be the positive constants defined in [E. A. Bender and E. R. Canfield, J. Comb. Theory, Ser. A 43, 244- 257 (1986; Zbl 0606.05031)]. In [J. Comb. Theory, Ser. A 49, No. 2, 370- 380 (1988; Zbl 0657.05037)], E. A. Bender and N. C. Wormald observed the following pattern:
\[
T_ g(n)\sim t_ g (\beta n)^{5(g-1)/2} \gamma^ n,\quad P_ g(n) \sim p_ g (\beta n)^{5(g-1)/2} \gamma^ n,
\]
for all maps, 2-connected maps and smooth maps. In this paper, we show that many classes of maps fit the following modified pattern:
\[
T_ g(n) \sim \alpha t_ g (\beta n)^{5(g-1)/2} \gamma^ n,\quad P_ g(n) \sim \alpha p_ g (\beta_ n)^{5(g-1)/2} \gamma^ n.
\]
Reviewer: Z.Gao (Ottawa)
MSC:
| 05C30 | Enumeration in graph theory |
References:
| [1] | Arques, D., Relations fonctionelles et dénombrement des cartes pointées sur le tore, J. Combin. Theory Ser. B, 43, 253-274 (1987) · Zbl 0628.05040 |
| [2] | Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002 |
| [3] | Bender, E. A.; Canfield, E. R., The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, 43, 244-257 (1986) · Zbl 0606.05031 |
| [4] | Bender, E. A.; Canfield, E. R.; Robinson, R. W., The enumeration of maps on the torus and the projective plane, Canad. Math. Bull., 31, 257-271 (1988) · Zbl 0617.05036 |
| [5] | E. A. Bender, Z. C. Gao, and L. B. RichmondJ. Graph Theory; E. A. Bender, Z. C. Gao, and L. B. RichmondJ. Graph Theory · Zbl 0809.05060 |
| [6] | Bender, E. A.; Gao, Z. C.; Richmond, L. B., Submaps of maps. I. General 0-1 laws, J. Combin. Theory Ser. B, 55, 104-117 (1992) · Zbl 0810.05034 |
| [7] | Bender, E. A.; Gao, Z. C.; McCuaig, W. D.; Richmond, L. B., Submap of maps. II. Cyclically \(k\)-connected planar cubic maps, J. Combin. Theory Ser. B, 55, 118-124 (1992) · Zbl 0810.05035 |
| [8] | E. A. Bender, Z. C. Gao, L. B. Richmond, and N. C. Wormald; E. A. Bender, Z. C. Gao, L. B. Richmond, and N. C. Wormald · Zbl 0913.05041 |
| [9] | Bender, E. A.; Richmond, L. B., A survey of the asymptotic behaviour of maps, J. Combin. Theory Ser. B, 40, 297-329 (1986) · Zbl 0563.05033 |
| [10] | Bender, E. A.; Wormald, N. C., The asymptotic number of rooted nonseparable maps on a surface, J. Combin. Theory Ser. A, 49, 370-380 (1988) · Zbl 0657.05037 |
| [11] | Brown, W. G., On the enumeration of non-planar maps, Mem. Amer. Math. Soc., 65 (1966) · Zbl 0149.21201 |
| [12] | Gao, Z. C., The number of rooted 2-connected triangular maps on the projective plane, J. Combin. Theory Ser. B, 53, 130-142 (1991) · Zbl 0753.05043 |
| [13] | Gao, Z. C., The number of rooted triangular maps on a surface, J. Combin. Theory Ser. B, 52, 236-249 (1991) · Zbl 0751.05053 |
| [14] | Gao, Z. C., The asymptotic number of rooted 2-connected triangular maps on a surface, J. Combin. Theory Ser. B, 54, 102-112 (1992) · Zbl 0759.05051 |
| [15] | Z. C. GaoDiscrete Math.; Z. C. GaoDiscrete Math. · Zbl 0792.05072 |
| [16] | Jackson, D. M.; Visentin, T. I., A character theoretic approach to embeddings of rooted maps in an orientable surface of given genus, Trans. Amer. Math. Soc., 322, 343-363 (1990) · Zbl 0747.05008 |
| [17] | Jackson, D. M.; Visentin, T. I., Character theory and rooted maps in an orientable surface of given genus: face-coloured maps, Trans. Amer. Math. Soc., 322, 365-376 (1990) · Zbl 0738.05005 |
| [18] | Tutte, W. T., Graph Theory (1984), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0554.05001 |
| [19] | Tutte, W. T., A census of planar triangulations, Canad. J. Math., 14, 21-38 (1962) · Zbl 0103.39603 |
| [20] | Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249-271 (1963) · Zbl 0115.17305 |
| [21] | Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74 (1968) · Zbl 0157.31101 |
| [22] | Walsh, T. R.S; Lehman, A. B., Counting rooted maps by genus, I, II, J. Combin. Theory Ser. B, 13, 122-141 (1972) · Zbl 0228.05108 |
| [23] | Walsh, T. R.S; Lehman, A. B., Counting rooted maps by genus, III, J. Combin. Theory Ser. B, 18, 222-259 (1975) · Zbl 0299.05110 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
