2018/09/25 by Stéphane Bessy, Dieter Rautenbach, Bessy, Stéphane +1
Computer Science · Mathematics · #Advanced Algebra and Logic #Rings, Modules, and Algebras
paper · pdf · doi:10.48550/arxiv.1809.09565
An independent broadcast on a connected graph G is a function f:V(G)→ ℕ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 αb(G) of G is the largest weight ∑x∈ V(G)f(x) of an independent broadcast f on G. It is known that α(G)≤ αb(G)≤ 4α(G) for every connected graph G, where α(G) is the independence number of G. If G has girth g and minimum degree δ, we show that αb(G)≤ 2α(G) provided that g≥ 6 and δ≥ 3 or that g≥ 4 and δ≥ 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 αb(G)≥ 2(1-(1)/(k))α(G). Our results imply that lower bounds on the girth and the minimum degree of a connected graph G can lower the fraction (αb(G))/(α(G)) from 4 below 2, but not any further.