A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σv∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ⊆ V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λb(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λb.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.