# 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 -> {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.
Published

2007-06-01

Issue

Section

Research Articles

The following license applies:

** Attribution CC BY**

This license lets others distribute, remix, tweak, and build upon your work, even commercially, as long as they credit you for the original creation.