Dominating and irredundant broadcasts in graphs

A broadcast on a nontrivial connected graph G=(V,E) is a function f:V→{0,1,…,diam(G)} such that f(v)≤e(v) (the eccentricity of v) for all v∈V. The cost of f is σ(f)=∑v∈Vf(v). A broadcast f is dominating if each u∈V is at distance at most f(v) from a vertex v with f(v)≥1.We use properties of minimal dominating broadcasts to define the concept of an irredundant broadcast on G. We determine conditions under which an irredundant broadcast is maximal irredundant. Denoting the minimum costs of dominating and maximal irredundant broadcasts by γb(G) and irb(G) respectively, the definitions imply that irb(G)≤γb(G) for all graphs. We show that γb(G)≤54irb(G) for all graphs G.We also briefly consider the upper broadcast number Γb(G) and upper irredundant broadcast number IRb(G), and illustrate that the ratio IRb/Γb is unbounded for general graphs.