The Number of Ways to Assemble a Graph

Source abstract

Motivated by the question of how macromolecules assemble,the notion of an assembly tree of a graph is introduced. Given a graph $G$, the paper is concerned with enumerating the number of assembly trees of $G$, a problem that applies to the macromolecular assembly problem. Explicit formulas or generating functions are provided for the number of assembly trees of several families of graphs, in particular for what we call $(H,\phi)$-graphs. In some natural special cases, we use a powerful recent result of Zeilberger and Apagodu to provide recurrence relations for the diagonal of the relevant multivariate generating functions, and we use a result of Wimp and Zeilberger to find very precise asymptotic formulae for the coefficients of these diagonals. Future directions for reseach, as well as open questions, are suggested.