2015/04/05 by Yanxia Dong, Dong, Yanxia, Erfang Shan +4
Computer Science · Materials Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Supramolecular Self-Assembly in Materials #acm:05C20 #acm:05C69 #math.CO #msc:05C20 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1504.01078
19 pages
arxiv created 2015/04/05 · arxiv updated 2015/04/07
Let G=(V,A) be a digraph and k≥ 1 an integer. For u,v∈ 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∖ D is distance k-dominated by some vertex of D. The \em distance k-domination number of G, denoted by γk(G), is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB(n,d) and generalized Kautz digraphs GK(n,d) are good candidates for interconnection networks. Tian and Xu showed that \lceil n/∑j=0kdj\rceil≤ γk(GB(n,d))≤ \lceil n/dk\rceil and \lceil n /∑j=0kdj\rceil≤ γk(GK(n,d))≤ \lceil n/dk\rceil. In this paper we prove that every generalized de Bruijn digraph GB(n,d) has the distance k-domination number \lceil n/∑j=0kdj\rceil or \lceil n/∑j=0kdj\rceil+1, and the distance k-domination number of every generalized Kautz digraph GK(n,d) bounded above by \lceil n/(dk-1+dk)\rceil. Additionally, we present various sufficient conditions for γk(GB(n,d))=\lceil n/∑j=0kdj\rceil and γk(GK(n,d))=\lceil n/∑j=0kdj\rceil.