\(G\)-Designs Without Blocking Sets

Abstract

For an undirected graph \(G\) and a natural number \(n\), a \(G\)-design of order \(n\) is an edge partition of the complete graph \(K_n\) with \(n\) vertices into subgraphs \(G_1, G_2, \ldots\), each isomorphic to \(G\). A set \(T \subset V(K_n)\) is called a blocking set if it intersects the vertex set \(V(G_i)\) of each \(G_i\) in the decomposition but contains none of them. Extending previous work [J. Combin. Designs \(4 (1996), 135-142]\), where the authors proved that cycle designs admit no blocking sets, we establish that this result holds for all graphs \(G\). Furthermore, we show that for every graph \(G\) and every integer \(k \geq 2\), there exists a non-\(k\)-colorable \(G\)-design.