A note on distance domination numbers of graphs.
Fang Tian, Jun‐Ming Xu · Australas. J Comb. · 2009
Let k be a positive integer and G = (V,E) a connected graph of order n. A set D ⊆ V is called a distance k-dominating set of G if each x ∈ V (G)−D is within distance k from some vertex of D. The k-domination number of G, denoted by γk(G), is the minimum cardinality over all distance k-dominating sets. Determining γk(G) has a significant impact on an efficient design of routing protocols in networks and, moreover, computing γk(G) is NP-hard. This paper establishes some upper bounds for γk(G) and improves some known results.