Decompositions of complete multipartite graphs and group divisible designs into isomorphic factors

Abstract

<p>A multipartite graph Km₁, m₂, ..., mr (group divisible design GDD) is (t,d)-decomposable if it can be decomposed into t factors with the same diameter d. The graph Km₁, m₂, ..., mr (design GDD) is (t,d)-isodecomposable if the factors are moreover isomorphic. Km₁, m₂, ..., mr (GDD) is admissible for a given t if its number of edges (or blocks) is divisible by t. fr(t,d) or gr(t,d), respectively, is the minimum number of vertices of a (t,d)-decomposable or (t,d)-isodecomposable complete r-partite graph, respectively. gr(t,d) is the minimum number such that for every p ≥ gr(t,d) there exists a (t,d)-isodecomposable r-partite graph with p vertices, and hr(t,d) is the minimum number such that all admissible r-partite graphs with p ≥ hr (t,d) vertices are (t,d)-isodecomposable.</p> <p>We completely determine the spectrum of all bipartite and tripartite (2,d)-isodecomposable graphs. We show that f₂(2,d) = g₂(2,d) = g₂(2,d) =h₂(2,d) and f₃(2,d) = g₃(2,d) = g₃(2,d) for each d, that is possible, while h₃(2,2) = ∞ (i.e., for any given p, there is an admissible graph with more than p vertices which is not (2,2)-isodecomposable), h₃(2,3) = g₃(2,3) +2, h₃(2,4) = g₃(2,4) and h₃(2,5) = g₃(2,5) + 1.</p> <p>For complete four-partite graphs we completely determine the spectrum of (2, d)-isodecomposable graphs with at most one odd part. For the remaining admissible graphs, namely for those with all odd parts, we show that there is no such (2,5)-isodecomposable graph. For d = 2,3,4 we solve the problem in this class completely for the graphs Kn,n,n,m and Kn,n,m,m.</p> <p>For all r ≥ 5 we determine smallest (2,d)-isodecomposable r-partite graphs for all possible diameters and show that also in these cases always gr(2,d) = gr'(2,d). Some values of hr(2,d) are also determined.</p> <p>We furthermore prove that if a GDD with r ≥ 3 groups is (2,d)-isodecomposable, then d ≤ 4 or d = ∞. We show that for every admissible n there exists a (2,3)- and (2,4)-isodecomposable 3 - GDD(n,3), i.e., a GDD with 3 groups of cardinality n and block size 3.</p> <p>Finally, we determine the spectrum of the designs 3 - GDD(n,3) which are decomposable into unicyclic factors.</p>