Various Bounds for Liar’s Domination Number

• Autorzy: Abdollah Alimadadi , Doost Ali Mojdeh , Nader Jafari Rad
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

liar’s domination; diameter; regular graph; Nordhaus-Gaddum

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 629-641

Daty

wydano

2016-08-01

otrzymano

2015-01-11

poprawiono

2015-08-23

zaakceptowano

2015-10-01

online

2016-07-06

Twórcy

autor

Abdollah Alimadadi

• Department of Mathematics University of Tafresh, Tafresh, Iran

autor

Doost Ali Mojdeh

• Department of Mathematics University of Mazandaran, Babolsar, Iran

autor

Nader Jafari Rad

• Department of Mathematics Shahrood University of Technology, Shahrood, Iran

Bibliografia

• [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[Crossref]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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]
• [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[Crossref]
• [16] P.J. Slater, Liar’s domination, Networks 54 (2009) 70-74. doi:10.1002/net.20295[Crossref][WoS]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1878