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)\le 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)\ge 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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}{P}_n$ equals $m(n–1)$.