>
Fa   |   Ar   |   En
   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
  
 
 

Copyright 2023
Islamic World Science Citation Center
All Rights Reserved