Premium
Liar's domination
Author(s) -
Slater Peter J.
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20295
Subject(s) - dominating set , vertex (graph theory) , combinatorics , mathematics , graph , set (abstract data type) , discrete mathematics , computer science , programming language
Assume that each vertex of a graph G is the possible location for an “intruder” such as a thief, or a saboteur, a fire in a facility or some possible processor fault in a computer network. A device at a vertex v is assumed to be able to detect the intruder at any vertex in its closed neighborhood N[v] and to identify at which vertex in N[v] the intruder is located . One must then have a dominating set S ⊆ V ( G ), a set with ∪ v ∈ S N [ v ] = V ( G ), to be able to identify any intruder's location. If any one device can fail to detect the intruder, then one needs a double‐dominating set. This article introduces the study of liar's dominating sets, sets that can identify an intruder's location even when any one device in the neighborhood of the intruder vertex can lie, that is, any one device in the neighborhood of the intruder vertex can misidentify any vertex in its closed neighborhood as the intruder location. Liar's dominating sets lie between double‐dominating sets and triple‐dominating sets because every triple‐dominating set is a liar's dominating set, and every liar's dominating set must double dominate. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009