Distance domination of generalized de Bruijn and Kautz digraphs

Let G = (V,A) be a digraph and k ae 1 an integer. For u, v a V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by gamma (k) (G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs G (B) (n, d) and generalized Kautz digraphs G (K) (n, d) are good candidates for interconnection networks. Denote Delta (k) := (a (j=0) (k) d (j) )(-1). F. Tian and J. Xu showed that aOEn Delta (k) aOEe gamma (k) (G (B) (n, d)) ae currency aOEn/d (k)aOEe and aOEn Delta (k) aOEe ae currency gamma (k) (G (K) (n, d)) ae currency aOEn/d (k) aOEe. In this paper, we prove that every generalized de Bruijn digraph G (B) (n, d) has the distance k-domination number aOEn Delta (k) aOEe or aOEn Delta (k) aOEe+1, and the distance k-domination number of every generalized Kautz digraph G (K) (n, d) bounded above by aOEn/(d (k-1)+d (k) )aOEe. Additionally, we present various sufficient conditions for gamma (k) (G (B) (n, d)) = aOEn Delta (k) aOEe and gamma (k) (G (K) (n, d)) = aOE inverted right perpendicular Delta (k) inverted left perpendicular.