Boundary independent broadcasts in graphs

Abstract

A broadcast on a nontrivial 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$. The weight of $f$ is $\sigma (f)=\sum _{v\in V}f(v)$. A vertex $u$ hears $f$ from $v$ if $f(v)>0$ and $d(u,v)\le f(v)$. A broadcast $f$ is independent, or hearing independent, if no vertex $u$ with $f(u)>0$ hears $f$ from any other vertex $v$. We define a different type of independent broadcast, namely a boundary independent broadcast, as a broadcast $f$ such that, if a vertex $w$ hears $f$ from vertices $v_1,\dots ,v_k$, $k\ge 2$, then $d(w,v_i)=f(v_i)$ for each $i$. The maximum weights of a hearing independent broadcast and a boundary independent broadcast are the \textit{hearing independence broadcast number} ${\alpha }_h(G)$ and the boundary independence broadcast number ${\alpha }_{bn}(G)$, respectively.

We prove that ${\alpha }_{bn}(G)=\alpha (G)$ (the independence number) for any 2-connected bipartite graph $G$ and that ${\alpha }_{bn}(G)\le n–1$ for all graphs $G$ of order $n$, characterizing graphs for which equality holds. We compare ${\alpha }_{bn}$ and ${\alpha }_h$ and prove that although the difference ${\alpha }_h–{\alpha }_{bn}$ can be arbitrary, the ratio is bounded, namely ${\alpha }_h/{\alpha }_{bn}<2$, which is asymptotically best possible. We deduce that ${\alpha }_h(G)\le 2n–5$ for all connected graphs $G\ne P_n$ of order $n$, which improves an existing upper bound for ${\alpha }_h(G)$ when $\alpha (G)\ge n/2$.