On the $⟨r,s⟩$ Domination Number of a Graph

Abstract

Suppose a network facility location problem is modelled by means of an undirected, simple graph $G=(\mathcal{V}\mathcal{,}\mathcal{E})$ with $\mathcal{=}\{v_1,\dots ,v_n\}$. Let $\mathbf{r}=(r_1,\dots ,r_n)$ and $\mathbf{s}=(s_1,\dots ,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,\dots ,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,\dots ,n$.