On the Relations Between Liars’ Dominating and Set-sized Dominating Parameters

Abstract

We define the $(i,j)$-liars’ domination number of $G$, denoted by $LR(i,j)(G)$, to be the minimum cardinality of a set $L\subseteq V(G)$ such that detection devices placed at the vertices in $L$ can precisely determine the set of intruder locations when there are between 1 and $i$ intruders and at most $j$ detection devices that might “lie”.

We also define the $X(c_1,c_2,\dots ,c_t,\dots )$-domination number, denoted by ${\gamma }_{X(c_1,c_2,\dots ,c_t,\dots )}(G)$, to be the minimum cardinality of a set $D\subseteq V(G)$ such that, if $S\subseteq V(G)$ with $|S|=k$, then $|(\bigcup _{v\in S}N[v])\cap D|\ge c_k$. Thus, $D$ dominates each set of $k$ vertices at least $c_k$ times making ${\gamma }_{X(c_1,c_2,\dots ,c_t,\dots )}(G)$ a set-sized dominating parameter. We consider the relations between these set-sized dominating parameters and the liars’ dominating parameters.