On the \(\langle r,s \rangle\) Domination Number of a Graph

Abstract

Suppose a network facility location problem is modelled by means of an undirected, simple graph \(G = (\mathcal{V, E})\) with \(\mathcal = \{v_1, \ldots, v_n\}\). Let \(\mathbf{r} = (r_1, \ldots, r_n)\) and \(\mathbf{s} = (s_1, \ldots, s_n)\) be vectors of nonnegative integers and consider the combinatorial optimization problem of locating the minimum number, \(\gamma(\mathbf{r}, \mathbf{s}, G)\) (say), of commodities on the vertices of \(G\) such that at least \(s_j\) commodities are located in the vicinity of (i.e. in the closed neighbourhood of) vertex \(v_j\), with no more than \(r_j\) commodities placed at vertex \(v_j\) itself, for all \(j = 1, \ldots, n\). In this paper we establish lower and upper bounds on the parameter \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a general graph \(G\). We also determine this parameter exactly for certain classes of graphs, such as paths, cycles, complete graphs, complete bipartite graphs and establish good upper bounds on \(\gamma(\mathbf{r}, \mathbf{s}, G)\) for a class of grid graphs in the special case where \(r_j = r\) and \(s_j = s\) for all \(j = 1, \ldots, n\).