文摘
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 each vertex of VD is distance k-dominated by some vertex of D. The 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. Denote Δk:= (∑j=0kdj)−1. F. Tian and J. Xu showed that ⌈nΔk⌉ γk(GB(n, d)) ≤⌈n/dk⌉ and ⌈nΔk⌉ ≤ γk(GK(n, d)) ≤ ⌈n/dk⌉. In this paper, we prove that every generalized de Bruijn digraph GB(n, d) has the distance k-domination number ⌈nΔk⌉ or ⌈nΔk⌉+1, and the distance k-domination number of every generalized Kautz digraph GK(n, d) bounded above by ⌈n/(dk−1+dk)⌉. Additionally, we present various sufficient conditions for γk(GB(n, d)) = ⌈nΔk⌉ and γk(GK(n, d)) = ⌈nΔk⌉.