Decompositions of complete multipartite graphs into disconnected selfcomplementary factors

Abstract

We determine the spectrum of complete bipartite and tripartite graphs that are decomposable into disconnected selfcomplementary factors (isodecomposable). For r-partite graphs with r ≥ 4 we determine the smallest orders of graphs that are isodecomposable. We also prove that every complete r-partite graph with at least one even part is isodecomposable. For graphs with all odd parts we prove that if among the cardinalities of the parts there is exactly one that appears an odd number of times, then the graph is also isodecomposable. Finally, we present a class of graphs with all odd parts that are not isodecomposable.