Γ-Species and the Enumeration of $k$-Trees

  • Andrew Gainer-Dewar
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.

Author Biography

Andrew Gainer-Dewar, Carleton College
Visiting Assistant Professor of Mathematics
Published
2012-12-13
Article Number
P45