Liar's vertex-edge domination in subclasses of chordal graphs

Let [Formula: see text] be an undirected graph. The set [Formula: see text] is called the closed neighbourhood of a vertex [Formula: see text] and for an edge [Formula: see text], the closed neighbourhood of [Formula: see text] is the set [Formula: see text], which is denoted by [Formula: see text] or [Formula: see text]. A set [Formula: see text] is called liar’s vertex-edge dominating set of a graph [Formula: see text] if for every [Formula: see text], [Formula: see text] and for every pair of distinct edges [Formula: see text], [Formula: see text]. The notion of liar’s vertex-edge domination arises naturally from some applications in communication networks. Given a graph [Formula: see text], the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of [Formula: see text] of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We design two linear time algorithms for MinLVEDP in block graphs and proper interval graphs, respectively. On the negative side, we show that the decision version of liar’s vertex-edge domination problem is NP-complete for undirected path graphs.