{"ID":2870851,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.11775","arxiv_id":"2509.11775","title":"Liar's vertex-edge domination in unit disk graph","abstract":"Let $G=(V, E)$ be a simple undirected graph. A closed neighbourhood of an edge $e=uv$ between two vertices $u$ and $v$ of $G$, denoted by $N_G[e]$, is the set of vertices in the neighbourhood of $u$ and $v$ including $\\{u,v\\}$. A subset $L$ of $V$ is said to be liar's vertex-edge dominating set if $(i)$ for every edge $e\\in E$, $|N_G[e]\\cap L|\\geq 2$ and $(ii)$ for every pair of distinct edges $e,e'$, $|(N_G[e]\\cup N_G[e'])\\cap L|\\geq 3$. The minimum liar's vertex-edge domination problem is to find the liar's vertex-edge dominating set of minimum cardinality. In this article, we show that the liar's vertex-edge domination problem is NP-complete in unit disk graphs, and we design a polynomial time approximation scheme(PTAS) for the minimum liar's vertex-edge domination problem in unit disk graphs.","short_abstract":"Let $G=(V, E)$ be a simple undirected graph. A closed neighbourhood of an edge $e=uv$ between two vertices $u$ and $v$ of $G$, denoted by $N_G[e]$, is the set of vertices in the neighbourhood of $u$ and $v$ including $\\{u,v\\}$. A subset $L$ of $V$ is said to be liar's vertex-edge dominating set if $(i)$ for every edge...","url_abs":"https://arxiv.org/abs/2509.11775","url_pdf":"https://arxiv.org/pdf/2509.11775v1","authors":"[\"Debojyoti Bhattacharya\",\"Subhabrata Paul\"]","published":"2025-09-15T10:55:17Z","proceeding":"math.CO","tasks":"[\"math.CO\",\"cs.DS\"]","methods":"[]","has_code":false}