PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 629-641
Tytuł artykułu

Various Bounds for Liar’s Domination Number

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
629-641
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-01-11
poprawiono
2015-08-23
zaakceptowano
2015-10-01
online
2016-07-06
Twórcy
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1878
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.