Girth, minimum degree, independence, and broadcast independence

Document Type: Original paper

Authors

1 LIRMM

2 89069 Ulm, Germay

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 $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.

Keywords

Main Subjects