Down-linking(Kv,Γ)-designs to P3-designs

Abstract

Let Γ' be a subgraph of a graph Γ. We define a down-link from a(K_vΓ)-design B to a(K_n,Γ')-design.B' as a map f: B → B' mapping any block of B into one of its subgraphs. This is a new concept,closely related with both the notion of metamorphosis and that of embedding. In the present paper we study down-links in general and prove that any(K_v,Γ)-design might be down-linked to a(K _n,Γ')-design,provided that n is admissible and large enough. We also show that if Γ' = P₃,it is always possible to find a down-link to a design of order at most v + 3. This bound is then improved for several classes of graphs Γ,by providing explicit constructions.