A multipartite approach for the self-assembly of DNA graph structures

Abstract We consider a graph theory problem motivated by the self-assembly of DNA graph structures using branched junction molecules with flexible arms (called ‘tiles’ in the combinatorial model). More precisely, we want to determine a set of tiles that realizes a target graph G using the minimum number of bond-edge types so that no graph with order smaller than $$\vert V(G)\vert$$ can be realized; the parameter of interest is denoted by $$B_2(G)$$ . We present an approach that provides an upper bound for $$B_2(G)$$ using certain multipartite subgraphs of G . We provide some numerical conditions characterizing such multipartite graphs in terms of the degree of their vertices. Then, we apply our method to the graphs corresponding to the Platonic solids.