Average distance and generalised packing in graphs

作者：Dankelmann Peter^*

来源：Discrete Mathematics, 2010, 310(17-18): 2334-2344.

DOI：10.1016/j.disc.2010.05.006

• Average distance
• Packing number
• Distance-k domination

Let G be a connected finite graph. The average distance mu(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 beta(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 beta(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.

• 出版日期2010-9-28