×

Enumerating near-4-regular maps on the sphere and the torus. (English) Zbl 0979.05058

From the authors’ introduction: “Rooted 4-regular planar maps (or their duals: quadrangulations) have been investigated by many scholars such as W. T. Tutte [e.g., A census of planar maps, Can. J. Math. 15, 249-271 (1963; Zbl 0115.17305)], W. G. Brown [Enumeration of quadrangular dissections of the disk, Can. J. Math. 17, 302-317 (1965; Zbl 0138.19104)], R. C. Mullin and P. J. Schellenberg [The enumeration of \(c\)-nets via quadrangulations, J. Comb. Theory 4, 259-276 (1968)], and Y. Liu [Enumerative theory of maps (Kluwer, Boston) (1995); On the number of rooted \(c\)-nets, J. Comb. Theory, Ser. B 36, 118-123 (1984; Zbl 0538.05042)]. The aim of this paper is to extend the pioneers’ earlier works and investigate the exact number of rooted 4-regular maps on the sphere and the torus. The main results (…) are: (1) The enumerating function of rooted (near-)4-regular maps with given number of nonroot-vertex loops on the sphere is presented. With this, several known formulae are deduced (for example, that for trees by Tutte (loc. cit.)). (2) The number of rooted planar near-4-regular Eulerian maps is investigated and its relation with near-4-regular toroidal maps is revealed (the former is also a nonplanar map problem and never studied before). (3) Rooted (near-)4-regular toroidal maps without loops are counted with respect to the root-valency, the number of edges, the number of nonroot-vertex loops and inner faces. More generally, a formula for rooted (near-)4-regular maps on the torus with exactly \(k\) nonroot-vertex loops is given. In particular, some known results on the torus (for instance, a formula for one-faced maps due to T. R. S. Walsh and A. B. Lehman [Counting rooted maps by genus, I, II, III. J. Comb. Theory, Ser. B 13, 127-141, 192-218 (1972; Zbl 0228.05109 and Zbl 0228.05108) and ibid., Ser. B 18, 222-259 (1975; Zbl 0299.05110)] are deduced.” The counting uses the method introduced by Tutte, and extended by the reviewer [On the enumeration of non-planar maps. Mem. Am. Math. Soc. 65 (1966; Zbl 0149.21201)] and others: a functional equation satisfied by the “ordinary” generating function for the family of rooted maps is derived, and then solved by Lagrangian inversion. (In the authors’ terminology regular refers to the degrees of the vertices, not of the map faces).

MSC:

05C30 Enumeration in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arquès, D., Relations fonctionelles et dénombremant 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.; Richmond, L. R., The asymptotic number of rooted maps on a surface, J. Combin. Theory Ser. A, 63, 318-329 (1993) · Zbl 0777.05065
[5] 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
[6] 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
[7] Bender, E. A.; Wormald, N. C., The asymptotic number of rooted nonseparable maps on a given surface, J. Combin. Theory Ser. A, 49, 370-380 (1988) · Zbl 0657.05037
[8] Brown, W. G., Enumeration of nonseparable planar maps, Canad. J. Math., XV, 526-545 (1963) · Zbl 0115.40901
[9] Brown, W. G., On the number of nonplanar maps, Mem. Amer. Math. Soc., 65, 1-42 (1966) · Zbl 0149.21201
[10] Brown, W. G., Enumeration of quadrangular dissections of the disc, Canad. J. Math., 17, 302-317 (1965) · Zbl 0138.19104
[11] 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
[12] 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
[13] I.P. Goulden, D.M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983, pp. 17,18.; I.P. Goulden, D.M. Jackson, Combinatorial Enumeration, Wiley, New York, 1983, pp. 17,18. · Zbl 0519.05001
[14] Liu, Y., On the number of rooted \(c\)-nets, J. Combin. Theory, 36, 118-123 (1984) · Zbl 0538.05042
[15] Liu, Y., On the number of Eulerian planar maps, Acta Math. Sci., 12, 418-423 (1992) · Zbl 0774.05047
[16] Y. Liu, Rectilinear Embeddings: Theory and Methods, Science Press, Beijing, 1994 (in Chinese).; Y. Liu, Rectilinear Embeddings: Theory and Methods, Science Press, Beijing, 1994 (in Chinese).
[17] Liu, Y., A polyhedral theory on graphs, Acta Math. Sinica, 10, 136-142 (1994) · Zbl 0812.05017
[18] Liu, Y., Combinatorial invariants on graphs, Acta Math. Sinica, 11, 211-220 (1995) · Zbl 0838.05038
[19] Liu, Y., Embeddibility in Graphs (1995), Kluwer: Kluwer Boston
[20] Liu, Y., Enumerative Theory of Maps (1999), Kluwer: Kluwer Boston · Zbl 0990.05070
[21] Mullin, R. C.; Schellenberg, P. J., The enumeration of \(c\)-nets via quadrangulations, J. Combin. Theory, 4, 256-276 (1964) · Zbl 0183.52403
[22] Tutte, W. T., A census of planar triangulations, Canad. J. Math., 14, 21-38 (1962) · Zbl 0103.39603
[23] Tutte, W. T., A census of slicings, Canad. J. Math., 14, 708-722 (1962) · Zbl 0111.35202
[24] Tutte, W. T., A census of hamiltonian polygons, Canad. J. Math. Soc., 68, 402-417 (1962) · Zbl 0105.17601
[25] Tutte, W. T., A census of planar maps, Canad. J. Math., 15, 249-271 (1963) · Zbl 0115.17305
[26] Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc., 74, 64-74 (1968) · Zbl 0157.31101
[27] T. Walsh, A.B. Lehman, Counting rooted maps by genus I, II, J. Combin. Theory Ser. B 13 (1972) 122-141, 192-218.; T. Walsh, A.B. Lehman, Counting rooted maps by genus I, II, J. Combin. Theory Ser. B 13 (1972) 122-141, 192-218. · Zbl 0228.05109
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.