The distance domination of generalized de Bruijn and Kautz digraphs
| Autor: | Dong, Yanxia, Shan, Erfang, Min, Xiao |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\big \lceil n\big/\sum_{j=0}^kd^j\big\rceil\le \gamma_{k}(G_B(n,d))\le \big\lceil n/d^{k}\big\rceil$ and $\big \lceil n \big/\sum_{j=0}^kd^j\big\rceil\le \gamma_{k}(G_K(n,d))\le \big\lceil n/d^{k}\big\rceil$. In this paper we prove that every generalized de Bruijn digraph $G_B(n,d)$ has the distance $k$-domination number $\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$ or $\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil+1$, and the distance $k$-domination number of every generalized Kautz digraph $G_K(n,d)$ bounded above by $\big\lceil n\big/(d^{k-1}+d^{k})\big\rceil$. Additionally, we present various sufficient conditions for $\gamma_{k}(G_B(n,d))=\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$ and $\gamma_{k}(G_K(n,d))=\big\lceil n\big/\sum_{j=0}^kd^j\big\rceil$. Comment: 19 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|