Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Broadcast number

Sortuj według:

Ogranicz wyniki do:

New bounds for the broadcast domination number of a graph

100%

Brewster R., Mynhardt C., Teshima L.

Open Mathematics

2013

tom 11

nr 7

1334-1343

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.

Ograniczanie wyników

1 Open Mathematics

1 Brewster R.

1 Mynhardt C.

1 Teshima L.

1 2013

Wyniki wyszukiwania

New bounds for the broadcast domination number of a graph