Enumeration of m-ary cacti

DOI10.1006/AAMA.1999.0665MaRDI QIDQ1585488zbMATH OpenOpenAlexFDO

Authors Miklós Bóna, Michel Bousquet, Gilbert Labelle, Pierre Leroux

Publication date 16 November 2000

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9804119

zbMATH Keywords

plane cacti

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Generalized Ramsey theory (05C55)

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.

Recommendations

• On cyclic 〈m,n〉-enumerations
• Enumeration of \(M\)-partitions
• The enumeration of Coxeter elements
• Symmetric regular cacti-properties and enumeration
• Enumeration of Cayley graphs and digraphs
• Cayley theorem on trees enumeration
• Enumeration of labeled block-cactus graphs
• Enumeration of labelled \((k,m)\)-trees
• Enumerations of lattice animals and trees
• On the enumeration and congruences for \(m\)-ary partitions

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3821780 (Why is no real title available?)
• scientific article; zbMATH DE number 3181013 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• scientific article; zbMATH DE number 3198646 (Why is no real title available?)
• BRANCHED COVERS OF S² AND BRAID GROUPS
• Cacti, braids and complex polynomials
• Enumeration d'arbres et formules d'inversion de séries formelles
• Enumeration of (uni- or bicolored) plane trees according to their degree distribution
• Enumeration of planar constellations
• On asymmetric structures
• On the Number of Husimi Trees
• The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
• The dissimilarity characteristic of Husimi trees
• The number of plane trees
• Une demonstration combinatoire de la formule de Lagrange à deux variables

Cited in

(21)

• Enumeration of planar constellations
• The Grassmann-Berezin calculus and theorems of the matrix-tree type
• The combinatorial relationship between trees, cacti and certain connection coefficients for the symmetric group
• Weak separation, positivity and extremal Yangian invariants
• Counting unrooted loopless planar maps
• Refined enumeration of vertices among all rooted ordered \(d\)-trees
• On a conjecture for the signless Laplacian spectral radius of cacti with given matching number
• Enumerations, forbidden subgraph characterizations, and the split-decomposition
• Zeroth-order general Randić index of cactus graphs
• Some results concerning plane cacti.
• Enumeration of solid 2-trees according to edge number and edge degree distribution
• Counting trees using symmetries
• The mathematical life of Pierre Leroux
• Spanning forests and the \(q\)-state Potts model in the limit \(q \to 0\)
• Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment
• Decomposition numbers for finite Coxeter groups and generalised non-crossing partitions
• On the spectral radius of cacti with \(k\)-pendant vertices
• Memory efficient algorithms for cactus graphs and block graphs
• Two bijective proofs for the arborescent form of the Good-Lagrange formula and some applications to colored rooted trees and cacti
• Enumeration of Möbius type cyclic polyazulenoids
• Jeu de taquin of set-valued Young tableaux

This page was built for publication: Enumeration of \(m\)-ary cacti

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1585488)