The number of \(m\)-Husimi trees fixed by a permutation of the vertices (Q1893980): Difference between revisions

A Husimi tree is a simple graph (no loops or parallel edges) in which all the 2-connected components are simple cycles, a single edge counting as a 2-cycle. An \(m\)-Husimi tree is a Husimi tree all of whose cycles are of the same size, so that a 2-Husimi tree is an ordinary tree. The article under review gives a formula for the number of \(m\)-Husimi trees invariant under a given permutation of its vertices. Another such formula is obtained in the case where a vertex is distinguished as a root and not counted among the elements of the permutation. This work generalizes a similar result for ordinary trees [the author and \textit{J. Labelle}, On combinatorial structures kept fixed by the action of a given permutation, Stud. Appl. Math. 84, No. 2, 105-118 (1991; Zbl 0749.05003)]. The derivation of the formulas uses the theory of species of structures; the necessary part of the theory is summarized in the article.