A subset L subset of V of a graph G = (V, E) is called a liar's dominating set of G if (i) vertical bar N-G{[}u] boolean AND L vertical bar >= 2 for every vertex u is an element of V, and (ii) vertical bar N-G {[}u] boolean OR N-G{[}v]) boolean AND L vertical bar >= 3 for every pair of distinct vertices u, v is an element of V. The MIN LIAR Dom SET problem is to find a liar's dominating set of minimum cardinality of a given graph G and the DECIDE LIAR Dom SET problem is the decision version of the MIN LIAR Dom SET problem. The DECIDE LIAR DOM SET problem is known to be NP-complete for general graphs. In this paper, we first present approximation algorithms and hardness of approximation results of the MIN LIAR Dom SET problem in general graphs, bounded degree graphs, and p-claw free graphs. We then show that the DECIDE LIAR Dom SET problem is NP-complete for doubly chordal graphs and propose a linear time algorithm for computing a minimum liar's dominating set in block graphs. (C) 2015 Elsevier B.V. All rights reserved.