\(G\)-designs and related designs (Q1802138)

Let \(G\) be a graph with \(k\) vertices and \(\lambda K_ v\) the complete multigraph with \(v\) vertices in which any two distinct vertices are joined by exactly \(\lambda\) edges. A \((v,k,\lambda)\) \(G\)-design is an edge-disjoint decomposition of \(\lambda K_ v\) into \(b\) subgraphs isomorphic to \(G\). A \(G\)-design is balanced if each vertex belongs to exactly \(r\) subgraphs, and is resolvable if \(\lambda K_ v\) can be factorized into \(r\) \(G\)-factors (i.e., spanning subgraphs whose all components are isomorphic to \(G)\). An \((m,n,k,\lambda)\) multipartite \(G\)- design is an edge-disjoint decomposition of a complete multipartite graph with \(m\) parts of \(n\) vertices each, \(\lambda K^ n_ m\), into \(b\) subgraphs isomorphic to \(G\). Balanced and resolvable \((m,n,k,\lambda)\) \(G\)-designs are defined similarly. Necessary conditions for the existence of \(G\)-designs, bipartite \(G\)- designs, multipartite \(G\)-designs, and also of the corresponding balanced and resolvable designs are proved. Furthermore, a survey of the results concerning the existence of \(G\)-designs, bipartite and multipartite \(G\)- designs, balanced \(G\)-designs and resolvable \(G\)-designs is presented for \(G=K_ k\), \(C_ k\) (a cycle with \(k\) vertices), \(P_ k\) (a path with \(k\) vertices), and \(S_ k\) (a star with \(k\) vertices). Some unsolved problems and conjectures are also posed.