Average distances and distance domination numbers

Let kk be a positive integer and GG be a simple connected graph with order nn. The average distance μ(G)μ(G) of GG is defined to be the average value of distances over all pairs of vertices of GG. A subset DD of vertices in GG is said to be a kk-dominating set of GG if every vertex of V(G)−DV(G)−D is within distance kk from some vertex of DD. The minimum cardinality among all kk-dominating sets of GG is called the kk-domination number γk(G)γk(G) of GG. In this paper tight upper bounds are established for μ(G)μ(G), as functions of nn, kk and γk(G)γk(G), which generalizes the earlier results of Dankelmann [P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21–35] for k=1k=1.