Relating broadcast independence and independence

摘要

An independent broadcast on a connected graph G is a function f : V(G) -> N-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 alpha(b)(G) of G is the largest weight Sigma(x is an element of V(G)) f(x) of an independent broadcast f on G. Clearly, alpha(b)(G) is at least the independence number alpha(G) for every connected graph G. Our main result implies alpha(b)(G) <= 4 alpha(G). We prove a tight inequality and characterize all extremal graphs. (C) 2019 Elsevier B.V. All rights reserved.