Domination Parameters and Gallai-type Theorems for Directed Trees

Abstract

The lower domination number of a digraph \(D\), denoted by \(\gamma(D)\), is the least number of vertices in a set \(S\), such that \(O[S] = V(D)\). A set \(S\) is irredundant if for all \(x \in S\), \(|O[x] – O[S – x]| \geq 1\). The lower irredundance number of a digraph, denoted \(ir(D)\), is the least number of vertices in a maximal irredundant set. A Gallai-type theorem has the form \(x(G) + y(G) = n\), where \(x\) and \(y\) are parameters defined on \(G\), and \(n\) is the number of vertices in the graph. We characterize directed trees satisfying \(\gamma(D) + \Delta_+(D) = n\) and directed trees satisfying \(ir(D) + \Delta_+(D) = n\).