On the Power Domination Number of de Bruijn and Kautz Digraphs

摘要

Let G = (V, A) be a directed graph, and let S C V be a set of vertices. Let the sequence S = S_0 ⊆ S_1⊆ S_2 ⊆ •• • be defined as follows: S_1 is obtained from S_0 by adding all out-neighbors of vertices in S_0. For k ≥2, S_k is obtained from S_(k-1) by adding all vertices w such that for some vertex v ∈ S_(k-1), w is the unique out-neighbor of v in V S_(k-i). We set M(S) = S_0 ∪ S_1 ∪ ..., and call S a power dominating set for G if M(S) = V(G). The minimum cardinality of such a set is called the power domination number of G. In this paper, we determine the power domination numbers of de Bruijn and Kautz digraphs.