The Algorithmic Complexity of Domination Digraphs

Abstract

Let $G=(V,E)$ be an undirected graph and let $\pi =\{V_1,V_2,\dots ,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.