Universal third parts of any complete 2-graph and none of DK₅

Artur Fortuna
Zdzisław Skupień

Abstract. It is shown that there is no digraph \(F\) which could decompose the complete digraph on 5 vertices minus any 2-arc remainder into three parts isomorphic to \(F\) for each choice of the remainder. On the other hand, for each \(n\ge3\) there is a universal third part \(F\) of the complete 2-graph \(^2K_n\) on \(n\) vertices, i.e., for each edge subset \(R\) of size \(|R|=\|^2K_n\| \bmod 3\), there is an \(F\)-decomposition of \(^2K_n-R\). Using an exhaustive computer-aided search, we find all, exactly six, mutually nonisomorphic universal third parts of the 5-vertex 2-graph. Nevertheless, none of their orientations is a universal third part of the corresponding complete digraph.

Keywords: decomposition, remainder, universal parts, isomorphic parts.

Mathematics Subject Classification: 05C35, 05C70.

Full text (pdf)