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.
@article{bwmeta1.element.doi-10_7151_dmgt_1878,
author = {Abdollah Alimadadi and Doost Ali Mojdeh and Nader Jafari Rad},
title = {Various Bounds for Liar's Domination Number},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {629-641},
zbl = {1339.05274},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1878}
}
Abdollah Alimadadi; Doost Ali Mojdeh; Nader Jafari Rad. Various Bounds for Liar’s Domination Number. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 629-641. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1878/
[1] D. Auger, Induced paths in twin-free graphs, Electron. J. Combin. 15 #N17 (2008). | Zbl 1160.05316
[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). | Zbl 0890.05001
[4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs, Advanced Topics (Marcel Dekker, Inc., New York, 1998). | Zbl 0883.00011
[5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graph (Marcel Dekker, Inc., New York, 1998). | Zbl 0890.05002
[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[Crossref] | Zbl 1008.94028
[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[Crossref] | Zbl 1256.05124
[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[Crossref] | Zbl 1105.94342
[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[Crossref] | Zbl 1259.05131
[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[WoS][Crossref] | Zbl 1297.90170
[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[Crossref] | Zbl 1263.05074
[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[WoS][Crossref] | Zbl 1284.05308
[14] M.L. Roden and P.J. Slater, Liar’s domination and the domination continuum, Congr. Numer. 190 (2008) 77-85. | Zbl 1181.05073
[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[Crossref] | Zbl 1211.05123
[16] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295[Crossref][WoS] | Zbl 1204.90061
[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[Crossref][WoS] | Zbl 1298.90122