×

Enumeration of \(m\)-ary cacti. (English) Zbl 0957.05056

From the authors’ abstract: The purpose of this paper is to enumerate various classes of cyclically colored \(m\)-gonal plane cacti, called \(m\)-ary cacti. This combinatorial problem is motivated by the topological classification of complex polynomials having at most \(m\) critical values, studied by Zvonkin and others. We obtain explicit formulae for both labelled and unlabelled \(m\)-ary cacti, according to (i) the number of polygons, (ii) the vertex-color distribution, (iii) the vertex-degree distribution of each color. We also enumerate \(m\)-ary cacti according to the order of their automorphism group. Using a generalization of Otter’s formula, we express the species of \(m\)-ary cacti in terms of rooted and of pointed cacti. A variant of the \(m\)-dimensional Lagrange inversion is then used to enumerate these structures. The method of Liskovets for the enumeration of unrooted planar maps can also be adapted to \(m\)-ary cacti.

MSC:

05C30 Enumeration in graph theory
05C55 Generalized Ramsey theory

Keywords:

plane cacti
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bergeron, F.; Labelle, G.; Leroux, P., Combinatorial Species and Tree-Like Structures. Combinatorial Species and Tree-Like Structures, Encyclopedia of Mathematics and Its Applications, 67 (1998), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0888.05001
[5] Chottin, L., Une démonstration combinatorie de la formule de Lagrange à deux variables, Discrete Math., 13, 215-224 (1975) · Zbl 0335.05013
[6] Chottin, L., Énumération d’arbres et formules d’inversion de séries formelles, J. Combin. Theory Ser. B, 31, 23-45 (1981) · Zbl 0466.05006
[8] Goulden, I. P.; Jackson, D. M., Combinatorial Enumeration (1983), John Wiley and Sons: John Wiley and Sons New York · Zbl 0519.05001
[9] Goulden, I. P.; Jackson, D. M., The Combinatorial Relationship Between Trees, Cacti and Certain Connection Coefficients for the Symmetric Group, European J. Combin., 13, 357-365 (1992) · Zbl 0804.05023
[10] Harary, F.; Norman, R. Z., Dissimilarity characteristic of Husimi trees, Ann. of Math., 58, 134-141 (1953) · Zbl 0051.40502
[11] Harary, F.; Palmer, G., Graphical Enumeration (1973), Academic: Academic New York · Zbl 0266.05108
[12] Harary, F.; Uhlenbeck, G. E., On the number of Husimi trees, Proc. Nat. Acad. Sci. U.S.A., 39, 315-322 (1953) · Zbl 0053.13104
[13] Husimi, K., Note on Mayer’s theory of cluster integrals, J. Chem. Phys., 18, 682-684 (1950)
[14] Khovanskii, A. G.; Zdravkovka, S., Branched covers of \(S^2\) and braid groups, J. Knot Theory Ramifications, 5, 55-75 (1996) · Zbl 0865.57001
[15] Labelle, G., On asymmetric structures, Discrete Math., 99, 141-164 (1992) · Zbl 0767.05011
[16] Labelle, G.; Leroux, P., Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Discrete Math., 157, 227-240 (1996) · Zbl 0868.05030
[17] Liskovets, V. A., A census of non-isomorphic planar maps, Colloq. Math. Soc. János Bolyai, 25, 479-494 (1981) · Zbl 0519.05040
[19] Scoins, H. I., The number of trees with nodes of alternate parity, Proc. Cambridge Philos. Soc., 58, 12-16 (1962) · Zbl 0122.41901
[20] Sherman, J.; Morrison, W. J., Adjustments of an inverse matrix corresponding to changes in the elements of a given row or a given column of the original matrix, Ann. Math. Stat., 20, 621 (1949)
[21] Stockmeyer, P. K., Enumeration of Graphs with Prescribed Automorphism Group (1971), University of Michigan: University of Michigan Ann Arbor
[22] Uhlenbeck, G. E.; Ford, G. W., Lectures in Statistical Mechanics (1963), American Mathematical Society: American Mathematical Society Providence · Zbl 0111.43802
[23] Walkup, D. W., The number of plane trees, Mathematica, 19, 200-204 (1972) · Zbl 0253.05106
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.