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.

Abstract Kirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet, in comparison with Steiner triple systems, little is known about their automorphism groups. In particular, there is no known congruence class representing the orders of a KTS with a number of automorphisms at least close to the number of points. We partially fill this gap by proving that whenever $$v \equiv 39$$ v≡39 (mod 72), or $$v \equiv 4^e48 + 3$$ v≡4e48+3 (mod $$4^e96$$ 4e96 ) and $$e \ge 0$$ e≥0 , there exists a KTS onvpoints having at least $$v-3$$ v-3 automorphisms. This is only one of the consequences of an investigation on the KTSs with an automorphism groupGacting sharply transitively on all but three points. Our methods are all constructive and yield KTSs which in many cases inherit some of the automorphisms ofG, thus increasing the total number of symmetries. To obtain these results it was necessary to introduce new types of difference families (the doubly disjoint ones) and difference matrices (the splittable ones) which we believe are interesting by themselves.