|
|
|
|
girth, minimum degree, independence, and broadcast independence
|
|
|
|
|
|
|
|
نویسنده
|
bessy stephane ,rautenbach dieter
|
|
منبع
|
communications in combinatorics and optimization - 2019 - دوره : 4 - شماره : 2 - صفحه:131 -139
|
|
چکیده
|
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.
|
|
کلیدواژه
|
broadcast independence ,independence ,packing
|
|
آدرس
|
laboratoire d'informatique, de robotique et de microelectronique de montpellier, france, ulm university, institute of optimization and operations research, germay
|
|
پست الکترونیکی
|
dieter.rautenbach@uni-ulm.de
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Authors
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|