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

Voir la notice de l'article provenant de la source Library of Science

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if ⋃_v ∈ 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.
Keywords: liar’s domination, diameter, regular graph, Nordhaus-Gaddum 
@article{DMGT_2016_36_3_a8,
     author = {Alimadadi, Abdollah and Mojdeh, Doost Ali and Rad, Nader Jafari},
     title = {Various {Bounds} for {Liar{\textquoteright}s} {Domination} {Number}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {629--641},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a8/}
}
TY  - JOUR
AU  - Alimadadi, Abdollah
AU  - Mojdeh, Doost Ali
AU  - Rad, Nader Jafari
TI  - Various Bounds for Liar’s Domination Number
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 629
EP  - 641
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a8/
LA  - en
ID  - DMGT_2016_36_3_a8
ER  - 
%0 Journal Article
%A Alimadadi, Abdollah
%A Mojdeh, Doost Ali
%A Rad, Nader Jafari
%T Various Bounds for Liar’s Domination Number
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 629-641
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a8/
%G en
%F DMGT_2016_36_3_a8
Alimadadi, Abdollah; Mojdeh, Doost Ali; Rad, Nader Jafari. Various Bounds for Liar’s Domination Number. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 629-641. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a8/