TY - JOUR
ID - 13855
TI - Girth, minimum degree, independence, and broadcast independence
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Bessy, Stephane
AU - Rautenbach, Dieter
AD - LIRMM
AD - 89069 Ulm, Germay
Y1 - 2019
PY - 2019
VL - 4
IS - 2
SP - 131
EP - 139
KW - broadcast independence
KW - independence
KW - packing
DO - 10.22049/cco.2019.26346.1098
N2 - 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)\leq \alpha_b(G)\leq 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)\leq 2\alpha(G)$ provided that $g\geq 6$ and $\delta\geq 3$ or that $g\geq 4$ and $\delta\geq 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 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.
UR - http://comb-opt.azaruniv.ac.ir/article_13855.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13855_71bcf08def5ae349eb3026397d2e7723.pdf
ER -