{"ID":2897386,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.04721","arxiv_id":"2507.04721","title":"Liar's vertex-edge domination in subclasses of chordal graphs","abstract":"Let $G=(V, E)$ be an undirected graph. The set $N_G[x]=\\{y\\in V|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$, $|N_G[e_i]\\cap L|\\geq 2$ and for every pair of distinct edges $e_i,e_j\\in E$, $|(N_G[e_i]\\cup N_G[e_j])\\cap L|\\geq 3$. The notion of liar's vertex-edge domination arises naturally from some applications in communication networks. Given a graph $G$, the \\textsc{Minimum Liar's Vertex-Edge Domination Problem} (\\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 \\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.","short_abstract":"Let $G=(V, E)$ be an undirected graph. The set $N_G[x]=\\{y\\in V|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...","url_abs":"https://arxiv.org/abs/2507.04721","url_pdf":"https://arxiv.org/pdf/2507.04721v1","authors":"[\"Debojyoti Bhattacharya\",\"Subhabrata Paul\"]","published":"2025-07-07T07:32:28Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}