Decompositions Of Kn(t) For Graph-Pairs Of Order 4 And 5

Let F and H be two non-isomorphic simple graphs based on the same vertex set without isolated vertices. If H = Fc, the complement group of F, then we call (F, H) a graph-pair. Given a graph G, a decomposition of G concerning graph-pair (F, H) (briefly, a (F, H)-decomposition of G ) is defined to be a pair (V(G), V) where V(G) is the vertex set of G and "D is a collection of subgraphs of G isomorphic to F or H which satisfy the properties: (1) {E(D} : D € V} forms a partition of E(G); (2) F and H are isomorphic to at least one subgraph of V.Recently, Abueida and Daven made an investigation into the existence of a graph-pair decomposition of Kn, the complete graph on n vertices. They solved the existence problem completely for all graph-pairs of order 4 and 5. As a generalization, it is given in this paper the. necessary and sufficient conditions of the existence of a (F, H)-decomposition of Kn(t] for all graph-pairs of order 4 and 5. Here, Kn(t] is the complete n-partite graph each of whose vertex classes has size t, when t - 1 Kn(t) = Kn.