Bessy, S., Rautenbach, D. (2019). Girth, minimum degree, independence, and broadcast independence. Communications in Combinatorics and Optimization, (), -. doi: 10.22049/cco.2019.26346.1098

Stéphane Bessy; Dieter Rautenbach. "Girth, minimum degree, independence, and broadcast independence". Communications in Combinatorics and Optimization, , , 2019, -. doi: 10.22049/cco.2019.26346.1098

Bessy, S., Rautenbach, D. (2019). 'Girth, minimum degree, independence, and broadcast independence', Communications in Combinatorics and Optimization, (), pp. -. doi: 10.22049/cco.2019.26346.1098

Bessy, S., Rautenbach, D. Girth, minimum degree, independence, and broadcast independence. Communications in Combinatorics and Optimization, 2019; (): -. doi: 10.22049/cco.2019.26346.1098

Girth, minimum degree, independence, and broadcast independence

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 $sumlimits_{xin V(G)}f(x)$ of an independent broadcast $f$ on $G$.

It is known that $alpha(G)leq alpha_b(G)leq 4alpha(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)leq 2alpha(G)$ provided that $ggeq 6$ and $deltageq 3$ or that $ggeq 4$ and $deltageq 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)geq 2left(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.