Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
• # Artykuł - szczegóły

## Discussiones Mathematicae Graph Theory

2016 | 36 | 3 | 629-641

## Various Bounds for Liar’s Domination Number

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.

EN

629-641

wydano
2016-08-01
otrzymano
2015-01-11
poprawiono
2015-08-23
zaakceptowano
2015-10-01
online
2016-07-06

### Twórcy

autor
• Department of Mathematics University of Tafresh, Tafresh, Iran
autor
• Department of Mathematics University of Mazandaran, Babolsar, Iran
autor
• 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]