Transversal designs and induced decompositions of graphs (Q286751)

Given two graphs \(G\) and \(H\), an induced \(H\)-decomposition of \(G\) is a collection \(\{H_1,\dots,H_k\}\) of pairwise edge-disjoint induced subgraphs of \(G\) such that each \(H_i\) is isomorphic to \(H\) for \(1\leq i\leq k\) and the edge set of \(G\) is a union of the edge sets of \(H_1,\dots,H_k\). Except when \(H\) is the complete graph on \(2\) vertices, not every graph \(G\) has an \(H\)-decomposition.NEWLINENEWLINEThe following interesting problem was proposed by \textit{J. A. Bondy} and \textit{J. L. Szwarcfiter} [J. Graph Theory 72, No. 3--4, 462--477 (2013; Zbl 1261.05082)]: given a non-complete graph \(H\) with \(v\) vertices and \(n\geq v\), what is the largest number of edges \(ex^{\ast}(n,H)\) of a graph on \(n\) vertices that has an induced \(H\)-decomposition ? \textit{N. Cohen} and \textit{Z. Tuza} [ibid. 78, No. 2, 97--107 (2015; Zbl 1305.05119)] proved that for every graph \(H\), \({n\choose 2}-\mathrm{ex}^{\ast}(n,H)=o(n^2)\).NEWLINENEWLINEIn this paper, using design theoretic and combinatorial tools, the authors proved that when \(H\) is a complete multipartite graph, then \({n\choose 2}-\mathrm{ex}^{\ast}(n,H)=O(n)\). The paper concludes with several interesting directions (5 conjectures and 1 problem) for future research.