Assembly Number

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

The assembly number a(G) of a graph G gives the number of assembly trees from which G 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 C_n is a Catalan number and n!! is a double factorial.

See also

Construction Number, Rooted Tree

Explore with Wolfram|Alpha


Kainen, P. C. "Construction Numbers: How to Build a Graph?" 25 Feb, 2023., 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.

Subject classifications