Title of article :
Liar’s domination in graphs
Author/Authors :
Roden، نويسنده , , Miranda L. and Slater، نويسنده , , Peter J.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
7
From page :
5884
To page :
5890
Abstract :
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 paper considers 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.
Keywords :
domination , detection , Fault-tolerant reporting , location
Journal title :
Discrete Mathematics
Serial Year :
2009
Journal title :
Discrete Mathematics
Record number :
1599130
Link To Document :
بازگشت