 TOPICS # Assembly Number

Vince and Bóna (2012) define an assembly tree for a connected simple graph on nodes as a binary rooted tree with leavesTree Leaf and internal nodes and satisfying a number of additional properties. An assembly tree for describes a process motivated by considering the self-assembly of macromolecules performed by virus capsids in the host cell (Kainen 2023).

The assembly number of a graph gives the number of assembly trees from which can be built. These numbers therefore count ways to build up a graph from subgraphs induced by various subsets of the vertices (Kainen 2023).

The assembly numbers for a number of parametrized graph are summarized in the table below (cf. Vince and Bóna 2012), where is a Catalan number and is a double factorial.

 family OEIS assembly number complete bipartite graph A217523 complete graph A001147 complete tripartite graph A361072 cycle graph A001700 path graph A000108 star graph A000142 Construction Number, Rooted Tree

## Explore with Wolfram|Alpha More things to try:

## References

Kainen, P. C. "Construction Numbers: How to Build a Graph?" 25 Feb, 2023. https://arxiv.org/abs/2302.13186.Sloane, N. J. A. Sequences A000108, A000142, A001147, A001700, A217523, and A361072 in "The On-Line Encyclopedia of Integer Sequences."Vince, A. and Bóna, M. "The Number of Ways to Assemble a Graph." Electr. J. Combin. 19, No. 4, Article P54, 2012.

## Cite this as:

Weisstein, Eric W. "Assembly Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AssemblyNumber.html