Partitioning vertices into in- and out-dominating sets in digraphs (Q2197403)

Let \(D\) be a digraph with the vertex set \(V(D)\) and the arc set \(A(D)\). A set \(X\subseteq V(D)\) is an out-dominating set if every vertex not in \(X\) is adjacent from a vertex in \(X\). Similarly, a set \(X\subseteq V(D)\) is an in-dominating set if every vertex not in \(X\) is adjacent to a vertex in \(X\). Directed \(p\)-in \(q\)-out domatic partition is the problem that given a digraph \(D\) and positive integers \(p\) and \(q\), determines whether there exists a partition of the vertex set \(V(D)=I_1\cup\cdots\cup I_p\cup O_1\cup\cdots\cup O_q\) such that \(I_i\) are in-dominating sets of \(D\) for \(1\leq i\leq p\) and \(O_j\) are out-dominating sets of \(D\) for \(1\leq j\leq q\). The IOP problem is the problem that given a digraph \(D\), determines whether there exists a partition of the vertex set \(V(D)=I\cup O\) such that \(I\) is an in-dominating set and \(O\) is an out-dominating sets of \(D\). In this article, the authors posed the problem of directed \(p\)-in \(q\)-out domatic partition, which is a domatic partition problem for digraphs, and investigated the problem whether a given digraph has a partition of the vertices into in- and out-dominating sets. The authors derived the following results: (1) the IOP problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a linear-time algorithm for deciding the existence of such partition. In fact, it would be interesting to discuss the directed \(p\)-in \(q\)-out domatic partition for various kinds of digraphs.