Girth, minimum degree, independence, and broadcast independence

Abstract

An independent broadcast on a connected graph $G$ is a function $f:V(G)\to {\mathbb{N}}_0$ such that, for every vertex $x$ of $G$, the value $f(x)$ is at most the eccentricity of $x$ in $G$, and $f(x)>0$ implies that $f(y)=0$ for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$. The broadcast independence number ${\alpha }_b(G)$ of $G$ is the largest weight $\sum _{x\in V(G)}f(x)$ of an independent broadcast $f$ on $G$. It is known that $\alpha (G)\le {\alpha }_b(G)\le 4\alpha (G)$ for every connected graph $G$, where $\alpha (G)$ is the independence number of $G$. If $G$ has girth $g$ and minimum degree $\delta$, we show that ${\alpha }_b(G)\le 2\alpha (G)$ provided that $g\ge 6$ and $\delta \ge 3$ or that $g\ge 4$ and $\delta \ge 5$. Furthermore, we show that, for every positive integer $k$, there is a connected graph $G$ of girth at least $k$ and minimum degree at least $k$ such that ${\alpha }_b(G)\ge 2\left(1-\frac{1}{k}\right)\alpha (G)$. Our results imply that lower bounds on the girth and the minimum degree of a connected graph $G$ can lower the fraction $\frac{{\alpha }_b(G)}{\alpha (G)}$ from $4$ below $2$, but not any further.