Liar's vertex-edge domination in subclasses of chordal graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918085232951296 |
|---|---|
| author | Bhattacharya, Debojyoti Paul, Subhabrata |
| author_facet | Bhattacharya, Debojyoti Paul, Subhabrata |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04721 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Liar's vertex-edge domination in subclasses of chordal graphs Bhattacharya, Debojyoti Paul, Subhabrata Combinatorics Data Structures and Algorithms 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. |
| title | Liar's vertex-edge domination in subclasses of chordal graphs |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.04721 |