Lower Boundary Independent Broadcasts in Trees

Abstract

A broadcast on a connected graph $G=(V,E)$ is a function $f:V\to \{0,1,\dots ,\mathrm{diam}(G)\}$ such that $f(v)\le e(v)$ (the eccentricity of $v$) for all $v\in V$ if $|V|\ge 2$, and $f(v)=1$ if $V=\{v\}$. The cost of $f$ is $\sigma (f)={\sum }_{v\in V}f(v)$. Let $V_f$ denote the set of vertices $v$ such that $f(v)$ is positive. A vertex $u$ hears $f$ from $v\in V_f^{+}$ if the distance $d(u,v)\le f(v)$. When $f$ is a broadcast such that every vertex $x$ that hears $f$ from more than one vertex in $V_f^{+}$ also satisfies $d(x,u)\ge f(u)$ for all $u\in V_f^{+}$, we say that the broadcast only overlaps in boundaries. A broadcast $f$ is boundary independent if it overlaps only in boundaries. Denote by $i_{\mathrm{bn}}(G)$ the minimum cost of a maximal boundary independent broadcast. We obtain a characterization of maximal boundary independent broadcasts, show that $i_{\mathrm{bn}}(T^{\prime })\le i_{\mathrm{bn}}(T)$ for any subtree $T^{\prime }$ of a tree $T$, and determine an upper bound for $i_{\mathrm{bn}}(T)$ in terms of the broadcast domination number of $T$. We show that this bound is sharp for an infinite class of trees.

22 pages, 7 figures