Labelled and unlabelled enumeration of k-gonal 2-trees

摘要

In this paper, we generalize 2-trees by replacing triangles by quadrilaterals, pentagons or k-sided polygons (k-gons), where kgreater than or equal to3 is given. This generalization, to k-gonal 2-trees, is natural and is closely related, in the planar case, to some specializations of the cell-growth problem. Our goal is the labelled and unlabelled enumeration of k-gonal 2-trees according to the number n of k-gons. We give explicit formulas in the labelled case, and, in the unlabelled case, recursive and asymptotic formulas. (C) 2004 Elsevier Inc. All rights reserved.