×

The number of degree restricted maps on general surfaces. (English) Zbl 0792.05072

For a finite set \(D\) of positive integers with maximum exceeding 2 the author considers rooted maps with a root face and other “distinguished” faces “marked” by the distinct positive integers of a set \(I\); \(z_ I\) is a set of indeterminates indexed by \(I\); all faces except the root and distinguished faces have degree in \(D\). The generating functions for numbers of such rooted maps on orientable and nonorientable surfaces of type \(g=1-{12 \over \chi}\), where \(x\), \(y\), \(z_ I\) mark the number of edges and the degrees of the root and distinguished faces, are respectively \(\widehat M_ g(x,y,z_ I)=\sum_{j \geq 0} y^ j \widehat M^ j_ g(x,z_ I)\), \(\widetilde M_ g (x,y,z_ I)=\sum_{j \geq 0}y^ j \widetilde M^ j_ g (x,z_ I)\). “The planar cases have been studied by E. A. Bender and E. R. Canfield [The number of degree restricted rooted maps on the sphere, SIAM J. Discrete Math. 7, No. 1, 9-15 (1994)]. Using Brown’s result on radicals of a formal power series [On the existence of square roots in certain rings of power series, Math. Ann. 158, 82-89 (1965; Zbl 0136.025); On \(k\)-th roots in power series rings, ibid. 170, 327-333 (1967; Zbl 0144.035)] they derived algebraic equations which \(\widehat M_ 0(x,y,\varnothing)\) satisfies. We extend their results to general surfaces... Asymptotic results ... are also derived for some special sets \(D\)”.

MSC:

05C30 Enumeration in graph theory
Full Text: DOI

References:

[1] Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002
[2] 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
[3] E.A. Bender and E.R. Canfield, The number of degree restricted rooted maps on the sphere, SIAM J. Discrete Math., to appear.; E.A. Bender and E.R. Canfield, The number of degree restricted rooted maps on the sphere, SIAM J. Discrete Math., to appear. · Zbl 0794.05048
[4] Brown, W. G., On the existence of square roots in certain rings of power series, Math. Ann., 158, 82-89 (1965) · Zbl 0136.02503
[5] Gao, Z., The number of rooted triangular maps on a surface, J. Combin. Theory Ser. B, 52, 236-249 (1991) · Zbl 0751.05053
[6] Gao, Z., The asymptotic number of rooted 2-connected triangular maps on a surface, J. Combin. Theory Ser. B, 54, 102-112 (1992) · Zbl 0759.05051
[7] Hille, E., Analytic Function Theory, Vol. II (1962), Ginn and Company · Zbl 0102.29401
[8] Marcus, M.; Minc, H., A Survey of Matrix Theory and Matrix Inequalities (1964), Prindle, Weber & Schmidt: Prindle, Weber & Schmidt Boston, MA · Zbl 0126.02404
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.