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.
@article{10_37236_2644,
author = {Andrew Vince and Mikl\'os B\'ona},
title = {The number of ways to assemble a graph},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {4},
doi = {10.37236/2644},
zbl = {1267.05028},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2644/}
}
TY - JOUR
AU - Andrew Vince
AU - Miklós Bóna
TI - The number of ways to assemble a graph
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/2644/
DO - 10.37236/2644
ID - 10_37236_2644
ER -
%0 Journal Article
%A Andrew Vince
%A Miklós Bóna
%T The number of ways to assemble a graph
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2644/
%R 10.37236/2644
%F 10_37236_2644
Andrew Vince; Miklós Bóna. The number of ways to assemble a graph. The electronic journal of combinatorics, Tome 19 (2012) no. 4. doi: 10.37236/2644
