Twin Domination in Digraphs

Abstract

A vertex \(v\) in a digraph \(D\) out-dominates itself as well as all vertices \(u\) such that \((v,u)\) is an arc of \(D\); while \(v\) in-dominates both itself and all vertices \(w\) such that \((w,v)\) is an arc of \(D\). A set \(S\) of vertices of \(D\) is a twin dominating set of \(D\) if every vertex of \(D\) is out-dominated by some vertex of \(S\) and in-dominated by some vertex of \(S\). The minimum cardinality of a twin dominating set is the twin domination number \(\gamma^*(D)\) of \(D\). It is shown that \(\gamma^*(D) \leq \frac{2p}{3}\) for every digraph \(D\) of order \(p\) having no vertex of in-degree \(0\) or out-degree \(0\). Moreover, we give a Nordhaus-Gaddum type bound for \(\gamma^*\), and for transitive digraphs we give a sharp upper bound for the twin domination number in terms of order and minimum degree.

For a graph \(G\), the upper orientable twin domination number \(DOM^*(G)\) is the maximum twin domination number \(\gamma^*(D)\) over all orientations \(D\) of \(G\); while the lower orientable twin domination number \(dom^*(G)\) of \(G\) is the minimum such twin domination number. It is shown that for each graph \(G\) and integer \(c\) with \(dom^*(G) \leq c \leq DOM^*(G)\), there exists an orientation \(D\) of \(G\) such that \(\gamma^*(D) = c\).