Enumeration of m-ary cacti

DOI10.1006/AAMA.1999.0665zbMATH Open0957.05056arXivmath/9804119OpenAlexW1975206347MaRDI QIDQ1585488FDOQ1585488

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)

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.

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

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

zbMATH Keywords

plane cacti

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

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

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)