首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Relating broadcast independence and independence
Authors:S Bessy  D Rautenbach
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 xV(G)f(x) of an independent broadcast f on G. Clearly, αb(G) is at least the independence number α(G) for every connected graph G. Our main result implies αb(G)4α(G). We prove a tight inequality and characterize all extremal graphs.
Keywords:Corresponding author    Broadcast independence  Independence
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号