Opuscula Math. 33, no. 4 (2013), 685-696
http://dx.doi.org/10.7494/OpMath.2013.33.4.685

Opuscula Mathematica

# Universal third parts of any complete 2-graph and none of DK5

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)

• Artur Fortuna
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Krakow, Poland
• Zdzisław Skupień
• AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Krakow, Poland
• Revised: 2013-03-29.
• Accepted: 2013-04-08.