On the Upper Broadcast Domination Number

Abstract

A broadcast on a graph \(G\) is a function \(f: V \to \{0, \dots, diam(G)\}\) such that for every vertex \(v \in V(G)\), \(f(v) \leq e(v)\), where \(diam(G)\) denotes the diameter of \(G\) and \(e(v)\) denotes the eccentricity of vertex \(v\). The upper broadcast domination number of a graph is the maximum value of \(\sum_{v \in V} f(v)\) among all minimal broadcasts \(f\) for which each vertex of the graph is within distance \(f(v)\) from some vertex \(v\) having \(f(v) \geq 1\). We give a new upper bound on the upper broadcast domination number which improves a previous result of Dunbar et al. in [Broadcasts in graphs, Discrete Applied Mathematics 154 (2006) 59-75]. We also prove that the upper broadcast domination number of any grid graph \(G_{m,n} = P_m \Box P_n\) equals \(m(n – 1)\).