The number of \(m\)-Husimi trees fixed by a permutation of the vertices
type: Item
instance of: scholarly article
title: The number of \(m\)-Husimi trees fixed by a permutation of the vertices
zbMATH Open document ID: 0824.05031
DOI: 10.1016/0012-365X(94)00127-5
author: Ivan Constantineau
published in: Discrete Mathematics
publication date: 1995-09-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 773904
zbMATH Keywords: enumeration formula
zbMATH Keywords: Husimi tree
zbMATH Keywords: cycles
zbMATH Keywords: invariant under a given permutation
zbMATH Keywords: species of structures
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: Computation of the expected number of leaves in a tree having a given automorphism, and related topics
cites work: Self-similarity in the combinatorial theory of orthogonal polynomials
cites work: Q5752576
cites work: On Combinatorial Structures Kept Fixed by the Action of a Given Permutation
cites work: COMBINATORIAL PROBLEMS IN THE THEORY OF GRAPHS. II
cites work: COMBINATORIAL PROBLEMS IN THE THEORY OF GRAPHS. I
cites work: Q5682013
cites work: On the Number of Husimi Trees
cites work: Une théorie combinatoire des séries formelles
cites work: Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange
cites work: Q3037638
cites work: Q4020379
cites work: Q5625202
full work available at URL: 0012-365x(94)00127-5
OpenAlex ID: W2082434353
description: scientific article; zbMATH DE number 773904