Γ-Species and the Enumeration of k-Trees
Keywords:
graph theory, combinatorial species, k-trees
Abstract
We study the class of graphs known as k-trees through the lens of Joyal’s theory of combinatorial species (and a extension known as 'Γ-species' which incorporates data about 'structural' group actions). This culminates in a system of recursive functional equations giving the generating function for unlabeled k-trees which allows for fast, efficient computation of their numbers. Enumerations up to k=10 and n=30 (for a k-tree with n+k−1 vertices) are included in tables, and Sage code for the general computation is included in an appendix.