Halving Complete \(4\)-Partite Graphs

Dalibor Froncek1, Jozef Siran2
1 Department of Applied Mathematics FEI VSB-Technical University Ostrava 17. Listopadu 70833 Ostrava Czech Republic
2Department of Mathematics SvF Slovak Technical University Radlinského 11 813 68 Bratislava Slovakia

Abstract

We completely determine the spectrum (i.e. set of orders) of complete \(4\)-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete \(4\)-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter \(5\). As regards the remaining possible finite diameters, \(2, 3, 4\), we present partial results, focusing on decompositions of \(K_{n,n,n,m}\) and \(K_{n,n,m,m}\) for odd \(m\) and \(n\).