On the total liar's domination of graphs

Document Type : Original paper


1 Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran

2 Shahid Rajaee Teacher Training University


For a graph $G$, a set $L$ of vertices is called a total liar's domination if $|N_G(u)\cap L|\geq 2$ for any $u\in V(G)$ and $|(N_G(u)\cup N_G(v))\cap L|\geq 3$ for any distinct vertices $u,v\in V(G)$. The total liar’s domination number is the cardinality of a minimum total liar’s
dominating set of $G$ and is denoted by $\gamma_{TLR}(G)$. In this paper we study the total liar's domination numbers of join and products of graphs.


Main Subjects

[1] A. Alimadadi, M. Chellali, and D.A. Mojdeh, Liar’s dominating sets in graphs, Discrete Appl. Math. 211 (2016), 204–210.
[2] R. Diestel, Graph Theory, Springer-Verlag, New York, 1997.
[3] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
[4] B.S. Panda and S. Paul, Hardness results and approximation algorithm for total liar’s domination in graphs, J. Comb. Optim. 27 (2014), no. 4, 643–662.
[5] M.L. Roden and P.J. Slater, Liar’s domination and the domination continuum, Congr. Numer. 190 (2008), 77–85.
[6] , Liar’s domination in graphs, Discrete Math. 309 (2009), no. 19, 5884–5890.
[7] P.J. Slater, Liar’s domination, Networks 54 (2009), no. 2, 70–74.