On the difference between broadcast and multipacking numbers of graphs

Abstract

A dominating broadcast of a connected graph G = (V,E) is a function f : V → {0,1,..., diam(G)} such that f(ν) < e(ν) (the eccentricity of ν) for each ν ∈ V and such that each vertex is within distance f(ν) from a vertex v with f(ν) > 0. The cost of a broadcast f is σ(f) = ∑_ν∈f(ν)> and the broadcast number b(G) is the minimum cost of a dominating broadcast. A set M ⊆ V is called a multipacking of a connected graph G if, for each v ∈ V and each κ such that 1 < κ < diam(G), v is within distance κ of at most κ vertices in M. The multipacking number mp(G) is the maximum cardinality of a multipacking of G and is bounded above by 6(G). We show that b(G)/ mp(G) < 3 and that b(G) - mp(G) can be arbitrarily large.