Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21284220191201Girth, minimum degree, independence, and broadcast independence1311391385510.22049/cco.2019.26346.1098ENStephaneBessyLIRMMDieterRautenbach89069 Ulm, GermayJournal Article20180925An independent broadcast on a connected graph $G$<br />is a function $f:V(G)to mathbb{N}_0$<br />such that, for every vertex $x$ of $G$, <br />the value $f(x)$ is at most the eccentricity of $x$ in $G$,<br />and $f(x)>0$ implies that $f(y)=0$ <br />for every vertex $y$ of $G$ within distance at most $f(x)$ from $x$.<br />The broadcast independence number $alpha_b(G)$ of $G$<br />is the largest weight $sumlimits_{xin V(G)}f(x)$<br />of an independent broadcast $f$ on $G$.<br /><br />It is known that $alpha(G)leq alpha_b(G)leq 4alpha(G)$<br />for every connected graph $G$,<br />where $alpha(G)$ is the independence number of $G$.<br />If $G$ has girth $g$ and minimum degree $delta$,<br />we show that <br />$alpha_b(G)leq 2alpha(G)$<br />provided that <br />$ggeq 6$ and $deltageq 3$<br />or that $ggeq 4$ and $deltageq 5$.<br />Furthermore, <br />we show that, <br />for every positive integer $k$,<br />there is a connected graph $G$ of girth at least $k$ and minimum degree at least $k$ <br />such that <br />$alpha_b(G)geq 2left(1-frac{1}{k}right)alpha(G)$.<br />Our results imply that <br />lower bounds on the girth and the minimum degree<br />of a connected graph $G$<br />can lower the fraction $frac{alpha_b(G)}{alpha(G)}$<br />from $4$ below $2$, but not any further.http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf