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

EJ Cockayne


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.

Full Text:




  • There are currently no refbacks.

ISSN 2224-0004 (online); ISSN 0259-191X (print)

Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help