Constructing the minimum dominating sets of generalized de Bruijn digraphs

In a digraph G=(V,A)G=(V,A), a vertex uu is said to dominate its out-neighbors vv, that is, there is an arc (u,v)∈A(u,v)∈A. A set D⊆VD⊆V is a dominating set of GG if each vertex of V∖DV∖D is dominated by some vertex of DD. The domination number   of GG, denoted by γ(G)γ(G), is the minimum cardinality of a dominating set of GG. Generalized de Bruijn digraphs GB(n,d)GB(n,d) are good candidates for interconnection networks. Kikuchi and Shibata show that ⌈nd+1⌉≤γ(GB(n,d))≤⌈nd⌉. In this paper, by constructing a (consecutive) dominating set of a generalized de Bruijn digraph, we prove that its domination number has exactly two values, that is, γ(GB(n,d))=⌈nd+1⌉ or ⌈nd+1⌉+1. Additionally, using a related result in number theory, we provide a complete characterization of generalized de Bruijn digraphs with the domination number equal to ⌈nd+1⌉ or ⌈nd+1⌉+1. As a consequence of the above results, we prove a conjecture posed by Kikuchi and Shibata. The conjecture says that each generalized de Bruijn digraph has a minimum dominating set that is consecutive.