×

Liars’ domination and the domination continuum. (English) Zbl 1181.05073

Summary: Assume that each vertex of a graph \(G\) is the possible location for an “intruder” such as a thief, a saboteur, a fire in a facility or some possible processor fault in a multiprocessor network. Here a detection device at a vertex \(v\) is assumed to be able to detect the intruder situated at any vertex in its closed neighborhood \(N[v]\) and to identify at which vertex in \(N[v]\) the intruder is located. Indeed, the detection device can pinpoint the location(s) of however many intruders there are in \(N[v]\). The reliability problem considered here involves the situation in which a device in the neighborhood of an intruder vertex can misidentify (lie about) location(s) of the intruder(s). We define the \((i,j)\)-liars domination number of \(G\), denoted by \(\gamma_{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 are lying.
We also define the \((c_1,c_2,\dots,c_t,\dots)\)-domination number \(\gamma_{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|=i\), then \((\bigcup_{s\in S} N[s])\cap D|\geq c_i\), and we show relations among the \(\gamma_{LR(i,j)}(G)\) and \(\gamma_{c_1,c_2,\dots,c_t,\dots)}(G)\) parameters.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite