Liar’s domination in graphs under some operations

Sergio Jr. Rosales Canoy, Carlito Bancoyo Balandra


A set $S\subseteq V(G)$ is a liar's dominating set ($lds$) of graph $G$ if $|N_G[v]\cap S|\geq 2$ for every $v\in V(G)$ and $|(N_G[u]\cup N_G[v])\cap S|\geq 3$ for any two distinct vertices $u,v \in V(G)$. The liar's domination number of $G$, denoted by $\gamma_{LR}(G)$, is the smallest cardinality of a liar's dominating set of $G$. In this paper we study the concept of liar's domination in the join, corona, and lexicographic product of graphs.


liar's dominating set; liar's-domination number; join; corona; lexicographic product

Full Text:



T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs,

Monographs and textbooks in Pure and Applied Mathematics, Marcel Dekker, New York, NY, USA, 208(1998).

M. Nikodem, False alarm in fault-tolerant dominating sets in graphs, Opuscula Mathematica, 32(2012), 751--760.

P. J. Slater, Liar's domination, Networks, 54(2009), 70--74.

P. J. Slater and M. L. Roden, Liar's domination in graphs, Discrete Mathematics, 309(2008), 5884--5890.


Sponsored by Tamkang University | ISSN 0049-2930 (Print), ISSN 2073-9826 (Online) | Powered by MathJax