Vertices contained in all or in no Minimum Liar’s Dominating Sets of a Tree

Abstract

Let $G=(V,E)$ be a graph having at least $3$ vertices in each of its components. A set $L\subseteq V(G)$ is a liar’s dominating set if

1. $|N_G[v]\cap L|\ge 2$ for all $v\in V(G)$ and
2. $|(N_G[u]\cup N_G[v])\cap L|\ge 3$ for every pair $u,v\in V(G)$ of distinct vertices in $G$,

where $N_G[x]=\{y\in V\mid xy\in E\}\cup \{x\}$ is the closed neighborhood of $x$ in $G$. In this paper, we characterize the vertices that are contained in all or in no minimum liar’s dominating sets in trees. Given a tree $T$, we also propose a polynomial time algorithm to compute the set of all vertices which are contained in every minimum liar’s dominating set of $T$ and the set of all vertices which are not contained in any minimum liar’s dominating set of $T$.