The number of ways to assemble a graph (Q1953368)

Summary: 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 \textit{M. Apagodu} and \textit{J. Zeilberger} [Adv. Appl. Math. 37, No. 2, 139--152 (2006; Zbl 1108.05010)] to provide recurrence relations for the diagonal of the relevant multivariate generating functions, and we use a result of \textit{J. Wimp} and \textit{J. Zeilberger} [J. Math. Anal. Appl. 111, 162--176 (1985; Zbl 0579.05007)] to find very precise asymptotic formulae for the coefficients of these diagonals. Future directions for research, as well as open questions, are suggested.