An algorithm for the (r, s)-domination number of a tree

Abstract

Suppose that at most r units of some commodity may be positioned at any vertex
of a graph G = (V,E) while at least s (≥ r) units must be present in the vicinity (i.e.
closed neighbourhood) of each vertex. Suppose that the function f : V 7! {0, . . . , r},
whose values are the numbers of units stationed at vertices, satisfies the above requirement.
Then f is called an s-dominating r-function. We present an algorithm which
finds the minimum number of units required in such a function and a function which
attains this minimum, for any tree

Keywords: Domination, dominating function, s-dominating r-function.

ORiON Vol. 23 (1) 2007: pp. 51-58