The distance domination of generalized de Bruijn and Kautz digraphs

Abstract

Let $G=(V,A)$ be a digraph and $k\ge 1$ an integer. For $u,v\in 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 for each vertex of $V\setminus D$ is distance $k$-dominated by some vertex of $D$. The {\em 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. Tian and Xu showed that $\lceil n/{\sum }_{j=0}^k{d}^j\rceil \le {\gamma }_k(G_B(n,d))\le \lceil n/d^k\rceil$ and $\lceil n/{\sum }_{j=0}^k{d}^j\rceil \le {\gamma }_k(G_K(n,d))\le \lceil n/d^k\rceil$. In this paper we prove that every generalized de Bruijn digraph $G_B(n,d)$ has the distance $k$-domination number $\lceil n/{\sum }_{j=0}^k{d}^j\rceil$ or $\lceil n/{\sum }_{j=0}^k{d}^j\rceil +1$, and the distance $k$-domination number of every generalized Kautz digraph $G_K(n,d)$ bounded above by $\lceil n/(d^{k-1}+d^k)\rceil$. Additionally, we present various sufficient conditions for ${\gamma }_k(G_B(n,d))=\lceil n/{\sum }_{j=0}^k{d}^j\rceil$ and ${\gamma }_k(G_K(n,d))=\lceil n/{\sum }_{j=0}^k{d}^j\rceil$.

19 pages