Liar’s Domination in Graphs


  • Derya Dogan Durgan
  • Ferhan Nihan Altundag


A set D V (G) of a graph G = (V;E) is a liar's dominating
set if (1) for all v 2 V (G) jN[v] \ Dj 2 and (2) for every pair u; v 2 V (G) of distinct vertices, jN[u] [ N[v] \ Dj 3. In this paper, we consider the liar's domination number of some middle graphs. Every triple dominating set is a liar's dominating set and every liar's dominating set must be a double dominating set. So, the liar's dominating set lies between double dominating set and triple dominating set.


[1] D. Dogan. Average Lower Domination Number For Some Middle Graphs, International J. Math. Combin., 4(2012), 58-67.

[2] F. Harary and T. W. Haynes. Double Domination in Graphs, Ars Combinatoria, 55(2000), 201-213.

[3] B.S. Panda and S. Paul. Liar's domination in graphs: Complexity and algorithm, Discrete Applied Mathematics, 161(7{8)(2013), 1085-1092.

[4] M.L. Roden and P. J. Slater. Liar's domination in graphs, Discrete Mathematics, 309(19)(2009), 5884-5890.

[5] P. J. Slater. Liar's domination, Networks, 54(2)(2009), 70{74.
[6] P.J. Slater. Domination and location in acyclic graphs, Networks, 17(1987), 55-64.

[7] P.J. Slater. Dominating and reference sets in a graph, J. Math. Phys. Sci., 22 (1988), 445-455.

[8] P.J. Slater. Locating dominating sets and locating-dominating sets, In Y. Alavi, A. Schwenk (Eds.) Graph theory, combinatorics, and algorithms : proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (Vol. 2, pp. 1073-1079), Wiley-Intersci, New York, 1995.