On aggregation in multiset-based self-assembly of graphs

We continue the formal study of multiset-based self-assembly. The process of self-assembly of graphs, where iteratively new nodes are attached to a given graph, is guided by rules operating on nodes labelled by multisets. In this way, the multisets and rules model connection points (such as "sticky ends") and complementarity/affinity between connection points, respectively. We identify three natural ways (individual, free, and collective) to attach (aggregate) new nodes to the graph, and study the generative power of the corresponding self-assembly systems. For example, it turns out that individual aggregation can be simulated by free or collective aggregation. However, we demonstrate that, for a fixed set of connection points, collective aggregation is rather restrictive. We also give a number of results that are independent of the way that aggregation is performed. © 2010 Springer Science+Business Media B.V.