Menu
Let \(G = (V,E)\) be an undirected graph and let \(\pi = \{V_1, V_2, \ldots, V_k\}\) be a partition of the vertices \(V\) of \(G\) into \(k\) blocks \(V_i\). From this partition one can construct the following digraph \(D(\pi) = (\pi, E(\pi))\), the vertices of which correspond one-to-one with the \(k\) blocks \(V_i\) of \(\pi\), and there is an arc from \(V_i\) to \(V_j\) if every vertex in \(V_j\) is adjacent to at least one vertex in \(V_i\), that is, \(V_i\) dominates \(V_j\). We call the digraph \(D(\pi)\) the domination digraph of \(\pi\). A triad is one of the 16 digraphs on three vertices having no loops or multiple arcs. In this paper we study the algorithmic complexity of deciding if an arbitrary graph \(G\) has a given digraph as one of its domination digraphs, and in particular, deciding if a given triad is one of its domination digraphs. This generalizes results for the domatic number.