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]|\ge 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)+{\mathrm{\Delta }}_{+}(D)=n$ and directed trees satisfying $ir(D)+{\mathrm{\Delta }}_{+}(D)=n$.