Graph decompositions, handcuffed prisoners and balanced P-designs

Given decompositions of graphs G and H into subgraphs of a given kind, we construct such decompositions for G×H and G⊗H(the categorical product). In view of the fact that Km•n=Km×Kn∪Km⊗Kn, this implies some “product theorems” (see e.g. Corollary of Lemma 7′. Theorems 3.3′ 5 etc.) for block designs and other configurations. Specifically we are interested in balanced P-designs i.e. configurations corresponding to decompositions of “multicomplete” graphs into paths of given length. These are studied in a parallel to balanced incomplete block designs, a necessary condition for the existence of a resolvable balanced P-design is found, and the “product theorems” -techniques are used to generate these designs on the first, resp. first and second possible series of values. Also a method of constructing these designs from balanced incomplete block designs is exhibited. The question of cyclic and regular designs is studied, a necessary condition demonstrated and such designs are constructed for the first few values.