Embedding balanced P(3)-designs into balanced P(4)-designs

A P(v,k,1) is a P(k)-design of order v and block size k (every path has k vertices and k-1 edges). A P(v,k,1) is said to be "balanced", if every vertex meets the same number of paths [P.Hell, A. Rosa, "Graph decompositions, handcuffed prisoners, and balanced P-designs", Discrete Math. 2 (1972) 229-252]. If V is a subset of W with |V|=v<n=|W|, then we say that a P(v,k,1) (V,P) is "embedded" into a P(n,k+1,1) (W,E) if there exists an injective mapping f:P->E such that B is a subgraph of f(B) for every B subset of P. In this paper we give necessary and sufficient conditions for embedding balanced P(3)-designs into (balanced) P(4)-designs.

Un P(v,k,1) è un P(k)-design di ordine v e block size k (ogni path ha k vertici e k-1 spigoli). Si dice che un P(v,k,1) è "bilanciato" se tutti i vertici hanno lo stesso grado (numero di paths contenenti un vertice) [P.Hell, A. Rosa, "Graph decompositions, handcuffed prisoners, and balanced P-designs", Discrete Math. 2 (1972) 229-252]. Sia V sottoinsieme di W con V|=v<n=|W|. Si dice che un P(v,k,1) (V,P) è "immerso" in un P(n,k+1,1) (W,E) se esiste un'applicazione iniettiva f:P->E tale che, per ogni sottoinsieme B di P, <B> è un sottografo di <f(B)>. In questo lavoro si determinano condizioni necessarie e sufficienti affinchè si abbiano "immersioni" di P(3)-designs bilanciati in P(4)-designs bilanciati e non.