An asymptotic resolution of a problem of Plesník.

Fix d ≥ 3. We show the existence of a constant c > 0 such that any graph of diameter at most d has average distance at most d − c d 3 / 2 n , where n is the number of vertices. Moreover, we exhibit graphs certifying sharpness of this bound up to the choice of c. This constitutes an asymptotic solution to a longstanding open problem of Plesník. Furthermore we solve the problem exactly for digraphs if the order is large compared with the diameter. [ABSTRACT FROM AUTHOR]