Broadcasts and multipackings in trees
Abstract
A set M ⊆ V is called a multipacking of a graph G = (V, E) if, for each v ϵ V and each s such that 1 ≤ s ≤ diam(G), v is within distance s of at most s vertices in M. The multipacking number, denoted mp(G), is the maximum cardinality of a multipacking of G. A function f: V → {0, 1,⋯,diam(G)} with f(v) ≤ e(v) (the eccentricity of v) for all v ϵ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0 is a dominating broadcast of G. The cost of a broadcast f is σ(f) = Σvϵv f(v), and the broadcast number γb(G) is the minimum cost of a dominating broadcast. We prove that for any tree T, γb(T) = mp(T). This generalizes the well-known result of A. Meir and J. W. Moon [Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975), no. 1, 225-233; MR0401519 (53 #5346)] that the 2-packing number of any tree equals its domination number.
