Distance Domination Numbers of Generalized de Bruijn and Kautz Digraphs
Fang Tian, Jun‐Ming Xu · 2006
The distance l-domination number γl(G) of a strongly connected digraph G is the minimum number γ for which there is a set DV (G) with cardinality γ such that any vertex v / 2 D can be reached within distance l from some vertex in D. In this paper, we establish a lower bound and an upper bound for γl of a generalized de Bruijn digraph and a generalized Kautz digraph, and also give a sufficient condition for these digraphs whose γ2 are equal to the lower bounds. As a consequence, for the de Bruijn digraph B(d, k), we determine that γ2(B(d, k)) = d k d2+d+1 . At the end of this paper, we conjecture γ2(K(d, k)) = d k +d k 1 d2+d+1 .