Various Bounds for Liar’s Domination Number
Discussiones Mathematicae Graph Theory, Tome 36 (2016) no. 3, p. 629.

Voir la notice de l'article dans European Digital Mathematics Library

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.
Classification : 05C12, 05C69
Mots-clés : liar’s domination, diameter, regular graph, Nordhaus-Gaddum, liar's domination 
@article{DMGT_2016__36_3_285861,
     author = {Abdollah Alimadadi and Doost Ali Mojdeh and Nader Jafari Rad},
     title = {Various {Bounds} for {Liar{\textquoteright}s} {Domination} {Number}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {629},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     zbl = {1339.05274},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2016__36_3_285861/}
}
TY  - JOUR
AU  - Abdollah Alimadadi
AU  - Doost Ali Mojdeh
AU  - Nader Jafari Rad
TI  - Various Bounds for Liar’s Domination Number
JO  - Discussiones Mathematicae Graph Theory
PY  - 2016
SP  - 629
VL  - 36
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2016__36_3_285861/
LA  - en
ID  - DMGT_2016__36_3_285861
ER  - 
%0 Journal Article
%A Abdollah Alimadadi
%A Doost Ali Mojdeh
%A Nader Jafari Rad
%T Various Bounds for Liar’s Domination Number
%J Discussiones Mathematicae Graph Theory
%D 2016
%P 629
%V 36
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2016__36_3_285861/
%G en
%F DMGT_2016__36_3_285861
Abdollah Alimadadi; Doost Ali Mojdeh; Nader Jafari Rad. Various Bounds for Liar’s Domination Number. Discussiones Mathematicae Graph Theory, Tome 36 (2016) no. 3, p. 629. https://geodesic-test.mathdoc.fr/item/DMGT_2016__36_3_285861/