On the Broadcast Independence Number of Caterpillars

Abstract

Let $G$ be a simple undirected graph.A broadcast on $G$ isa function $f:V(G)\to \mathbb{N}$ such that $f(v)\le e\_G(v)$ holds for every vertex $v$ of $G$, where $e\_G(v)$ denotes the eccentricity of $v$ in $G$, that is, the maximum distance from $v$ to any other vertex of $G$.The cost of $f$ is the value $\mathrm{cost}(f)=\sum \_v\in V(G)f(v)$.A broadcast $f$ on $G$ is independent if for every two distinct vertices $u$ and $v$ in $G$, $d\_G(u,v)>\max \{f(u),f(v)\}$,where $d\_G(u,v)$ denotes the distance between $u$ and $v$ in $G$.The broadcast independence number of $G$ is then defined as the maximum cost of an independent broadcast on $G$. In this paper, we study independent broadcasts of caterpillars and give an explicit formula for the broadcast independence number of caterpillars having no pair of adjacent vertices with degree 2.