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

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| \geq 2 \) for all \( v \in V(G) \) and
2. \( |(N_G[u] \cup N_G[v]) \cap L| \geq 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 \).