Distance domination and generalized eccentricity in graphs with given minimum degree

Let G be a connected graph and k ∈ N. The k -distance domination number of G is the smallest cardinality of a set S of vertices such that every vertex of G is within distance k from some vertex of S. While for k=1, that is, for the ordinary domination number, the problem of finding asymptotically sharp upper bounds in terms of order and minimum degree of the graph has been solved, corresponding bounds for k > 1 have remained elusive. In this paper, we solve this problem and present an asymptotically sharp upper bound on the k -distance domination number of a graph in terms of its order and minimum degree, which significantly improves on bounds in the literature. We also obtain an asymptotically sharp upper bound on the p -radius of graphs in terms of order and minimum degree. For p ∈ N, the p -radius of G is defined as the smallest integer d such that there exists a set S of p vertices of G having the property that every vertex of G is within distance d of some vertex in S. We also present improved bounds for graphs of given order, minimum degree and maximum degree, for triangle-free graphs and for graphs not containing a 4 -cycle as a subgraph.