On the double competition number (Q1383383)

The double competition graph of a directed graph \(D=(V,A)\) is the graph \(G=(V,E)\) where \(xy\in E(G)\) if and only if for some \(u,v\in V(G)\), the arcs \(ux\), \(uy\) and \(xy\), \(yv\) belong to \(A(G)\). The author proved in [``Competition of graphs and clique dimensions'', Random Struct. Algorithms 1, No. 2, 183-198 (1990; Zbl 0764.05091)] that for almost all simple graphs over \(n\) vertices one needs \(\Omega (n^{4/3} (\log n)^{-4/3})\) extra vertices to obtain them as a double competition graph of a digraph. In the present paper, the author gives a construction showing that \(2n^{4/3}\) are always sufficient.