Let $G=(V,A)$ be a directed graph without parallel arcs, and let $S\subseteq V$ be a set of vertices. Let the sequence $S=S_0\subseteq S_1\subseteq S_2\subseteq\cdots$ be defined as follows: $S_1$ is obtained from $S_0$ by adding all out-neighbors of vertices in $S_0$. For $k\geqslant 2$, $S_k$ is obtained from $S_{ k-1}$ by adding all vertices $w$ such that for some vertex $v\in S_{ k-1}$, $w$ is the unique out-neighbor of $v$ in $V\setminus S_{ k-1}$. We set $M(S)=S_0\cup S_1\cup\cdots$, and call $S$ a \emph{ power dominating set} for $G$ if $M(S)=V(G)$. The minimum cardinality of such a set is called the \emph{ power domination number} of $G$. In this paper, we determine the power domination numbers of de Bruijn and Kautz digraphs.
Categories: cs.DM math.CO