# 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