## Abstract

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 language | English |
---|---|

Pages (from-to) | 2334-2344 |

Number of pages | 11 |

Journal | Discrete Mathematics |

Volume | 310 |

Issue number | 17-18 |

DOIs | |

Publication status | Published - 28 Sept 2010 |

Externally published | Yes |

## Keywords

- Average distance
- Distance-k domination
- Packing number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics