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/

[1] D. Auger, Induced paths in twin-free graphs, Electron. J. Combin. 15 #N17 (2008).

[2] J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics 244 (Springer-Verlag, London, 2008).

[3] G. Chartrand and L. Lesniak, Graphs and Digraphs, 4th Ed. (CRC Press, Bocz Raton, 2004).

[4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graph (Marcel Dekker, Inc., New York, 1998).

[6] T.W. Haynes, P.J. Slater and C. Sterling, Liar’s domination in ladders, Congr. Numer. 212 (2012) 45-56.

[7] I. Honkala, T. Laihonen and S. Ranto, On codes identifying sets of vertices in Hamming spaces, Des. Codes Cryptogr. 24 (2001) 193-204. doi:10.1023/A:1011256721935

[8] V. Junnila and T. Laihonen, Optimal identifying codes in cycles and paths, Graphs Combin. 28 (2012) 469-481. doi:10.1007/s00373-011-1058-6

[9] M.G. Karpovsky, K. Chakrabarty and L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 599-611. doi:10.1109/18.661507

[10] M. Nikodem, False alarms in fault-tolerant dominating sets in graphs, Opuscula Math. 32 (2012) 751-760. doi:10.7494/OpMath.2012.32.4.751

[11] B.S. Panda and S. Paul, Hardness results and approximation algorithm for total liar’s domination in graphs, J. Comb. Optim. 27 (2014) 643-662. doi:10.1007/s10878-012-9542-3

[12] B.S. Panda and S. Paul, Liar’s domination in graphs: Complexity and algorithm, Discrete Appl. Math. 161 (2013) 1085-1092. doi:10.1016/j.dam.2012.12.011

[13] B.S. Panda and S. Paul, A linear time algorithm for liar’s domination problem in proper interval graphs, Inform. Process. Lett. 113 (2013) 815-822. doi:10.1016/j.ipl.2013.07.012

[14] M.L. Roden and P.J. Slater, Liar’s domination and the domination continuum, Congr. Numer. 190 (2008) 77-85.

[15] M.L. Roden and P.J. Slater, Liar’s domination in graphs, Discrete Math. 309 (2009) 5884-5890. doi:10.1016/j.disc.2008.07.019

[16] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295

[17] J. Zhou, Z. Zhang, W. Wu and K. Xing, A greedy algorithm for the fault-tolerant connected dominating set in a general graph, J. Comb. Optim. 28 (2014) 310-319. doi:10.1007/s10878-013-9638-4