%0 Journal Article
%T Girth, minimum degree, independence, and broadcast independence
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Bessy, Stephane
%A Rautenbach, Dieter
%D 2019
%\ 12/01/2019
%V 4
%N 2
%P 131-139
%! Girth, minimum degree, independence, and broadcast independence
%K broadcast independence
%K independence
%K packing
%R 10.22049/cco.2019.26346.1098
%X 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 degreeof a connected graph $G$can lower the fraction $frac{alpha_b(G)}{alpha(G)}$from $4$ below $2$, but not any further.
%U http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf