Distance domination of generalized de Bruijn and Kautz digraphs (Q1692700): Difference between revisions

In a digraph $G=(v,A)$ a vertex $u$ distance $k$-dominates a vertex $v$ if the distance from $u$ to $v$ is at most $k$. The distance $k$-domination number is the minimum cardinality of a distance $k$-dominating set. A generalized de Bruijn graph $G_B (n,d)$ has vertex set $V = \{ 0, 1, \ldots, n-1 \}$ and $(x,y)$ is an arc in $A$ if $y$ is congruent to $dx+i$ modulo $n$ for some $i$ between 0 and $d-1$. Generalized Kautz graphs $G_K (n,d)$ are defined on the same $V$, but the arc set $A$ is defined by the congruence $-dx-i$ modulo $n$. It is proved that the distance $k$-dominating number for $G_B (n,d)$ is either $\lceil n\Delta_k \rceil$ or $\lceil n\Delta_k \rceil +1$, where $\Delta _k = ( \Sigma _{j=0}^k d^j )^{-1} $. Some sufficient conditions on the structure of $G_B$ are provided for the domination number to assume the smaller value. Corresponding necessary conditions are posed as an open problem. For generalized Kautz graphs $G_K (n,d)$ the sharp upper bound of $\lceil \frac{n}{d^k +d^{k-1} } \rceil $ for the distance $k$-dominating number is obtained constructively and the equality is conjectured.