Title of article :
Girth, minimum degree, independence, and broadcast independence
Author/Authors :
Bessy ، Stephane Laboratoire d Informatique, de Robotique et de Microelectronique de Montpellier , Rautenbach ، Dieter Institute of Optimization and Operations Research - Ulm University
From page :
131
To page :
139
Abstract :
An independent broadcast on a connected graph G is a function f:V(G)→N0 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−1k)α(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.
Keywords :
broadcast independence , independence , packing
Journal title :
Communications in Combinatorics and Optimization
Journal title :
Communications in Combinatorics and Optimization
Record number :
2696222
Link To Document :
بازگشت