Broadcast independence and packing in certain classes of trees

Abstract

Given a graph $G=(V,E)$ of diameter $d$, a broadcast is a function $f:V(G)\to \{0,1,\dots ,d\}$ where $f(v)$ is at most the eccentricity of $v$. A vertex $v$ is broadcasting if $f(v)>0$ and a vertex $u$ hears $v$ if $d(u,v)\le f(v)$. A broadcast is independent if no broadcasting vertex hears another vertex and is a packing if no vertex hears more than one vertex. The weight of $f$ is ${\sum }_{v\in V}f(v)$. We find the maximum weight independent and packing broadcasts for perfect $k$-ary trees, spiders, and double spiders as a partial answer to a question posed by Ahmane et al.

23 pages, 3 figures