Name
Abstract | ||
|---|---|---|
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 ab(G) of G is the largest weight Sigma(x is an element of V)(G) f(x) of an independent broadcast f on G. We describe an efficient algorithm that determines the broadcast independence number of a given tree. Furthermore, we show NP-hardness of the broadcast independence number for planar graphs of maximum degree four, and hardness of approximation for general graphs. Our results solve problems posed by Dunbar (2006), Hedetniemi (2006), and Ahmane et al. (2018). (C) 2022 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.dam.2022.03.001 | DISCRETE APPLIED MATHEMATICS |
Keywords | DocType | Volume |
Broadcast independence | Journal | 314 |
ISSN | Citations | PageRank |
0166-218X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Bessy | 1 | 0 | 0.34 |
| Dieter Rautenbach | 2 | 946 | 138.87 |