Opuscula Math. 33, no. 4 (2013), 685-696
Universal third parts of any complete 2-graph and none of DK5
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.
- Received: 2012-06-28.
- Revised: 2013-03-29.
- Accepted: 2013-04-08.