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

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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\vert V(G)\vert$$\end{document} can be realized; the parameter of interest is denoted by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_2(G)$$\end{document}. We present an approach that provides an upper bound for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B_2(G)$$\end{document} 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.