Liar's vertex-edge domination in unit disk graph

Read full text
Authors: Debojyoti Bhattacharya, Subhabrata Paul
Cited by: 0

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.

Fields of Study & Subjects

Advanced Graph Theory Research Optimization and Search Problems Complexity and Algorithms in Graphs

Publication details

Journal / source
Discussiones Mathematicae Graph Theory
Volume
46
Issue
3
Pages
835–835
Publication date
1 January 2026
Language
EN