Average distance and generalised packing in graphs

Let GG be a connected finite graph. The average distance  μ(G)μ(G) of GG is the average of the distances between all pairs of vertices of GG. For a positive integer kk, a kk-packing   of GG is a subset SS of the vertex set of GG such that the distance between any two vertices in SS is greater than kk. The kk-packing number  βk(G)βk(G) of GG is the maximum cardinality of a kk-packing of GG. We prove upper bounds on the average distance in terms of βk(G)βk(G) and show that for fixed kk the bounds are, up to an additive constant, best possible. As a corollary, we obtain an upper bound on the average distance in terms of the kk-domination number  , the smallest cardinality of a set SS of vertices of GG such that every vertex of GG is within distance kk of some vertex of SS.