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

Let $G=(V,E)$ be an undirected graph. The set $N_G[x]=\{y\in V\mathrm{\mid }xy\in E\}\cup \{x\}$ is called the closed neighbourhood of a vertex $x\in V$ and for an edge $e=xy\in E$, the closed neighbourhood of $e$ is the set $N_G[x]\cup N_G[y]$, which is denoted by $N_G[e]$ or $N_G[xy]$. A set $L\subseteq V$ is called \emph{liar’s vertex-edge dominating set} of a graph $G=(V,E)$ if for every $e_i\in E$, $\mathrm{\mid }{N}_G[e_i]\cap L\mathrm{\mid }\ge 2$ and for every pair of distinct edges $e_i,e_j\in E$, $\mathrm{\mid }(N_G[e_i]\cup N_G[e_j])\cap L\mathrm{\mid }\ge 3$. The notion of liar’s vertex-edge domination arises naturally from some applications in communication networks. Given a graph $G$, the $\text{textsc}MinimumLia{r}^{\mathrm{\prime }}sVertex-EdgeDominationProblem$ ($\text{textsc}MinLVEDP$) asks to find a liar’s vertex-edge dominating set of $G$ of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We design two linear time algorithms for $\text{textsc}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.