Average distance and generalised packing in graphs

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Let G be a connected finite graph. The average distance μ(G) of G is the average of the distances between all pairs of vertices of G. For a positive integer k, a k-packing of G is a subset S of the vertex set of G such that the distance between any two vertices in S is greater than k. The k-packing number βk(G) of G is the maximum cardinality of a k-packing of G. We prove upper bounds on the average distance in terms of βk(G) and show that for fixed k 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 k-domination number, the smallest cardinality of a set S of vertices of G such that every vertex of G is within distance k of some vertex of S.

Original languageEnglish
Pages (from-to)2334-2344
Number of pages11
JournalDiscrete Mathematics
Issue number17-18
Publication statusPublished - 28 Sept 2010
Externally publishedYes


  • Average distance
  • Distance-k domination
  • Packing number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Average distance and generalised packing in graphs'. Together they form a unique fingerprint.

Cite this