We prove that the class of trees with unique minimum edge-vertex dominating sets is equivalent to the class of trees with unique minimum paired dominating sets.
A subset \(D\) of \(V_{{ {G}}}\) is said to be a dominating set of a graph \({ {G}}=( {V_{{ {G}}}}, {E_{{ {G}}}})\) if each vertex belonging to the set \( {V_{{ {G}}}}\setminus D\) has a neighbour in \(D\) [1, 20]. A set \(D\subseteq {V_{{ {G}}}}\) is a paired-dominating set of \(G\) if \(D\) is a dominating set of \(G\) and the induced subgraph \({ {G}}[D]\) has a perfect matching. The paired-domination number of \(G\), denoted by \(\gamma_{\rm pr}({ {G}})\), is defined to be the minimum cardinality of a paired-dominating set \(D\) of \(G\), and any minimum paired dominating set of \(G\) is referred to as a \(\gamma_{\rm pr}\)-set [12, 13]. Next, an edge \(e \in {E_{{ {G}}}}\) is said to \(ev\)-dominate a vertex \(v \in {V_{{ {G}}}}\) if \(e\) is incident to \(v\) or \(e\) is incident to a vertex adjacent to \(v\). A set \(M \subseteq {E_{{ {G}}}}\) is an edge-vertex dominating set (or simply, an \(ev\)-dominating set) of \(G\) if each vertex of \(G\) is \(ev\)-dominated by some edge in \(M\). Finally, the edge-vertex domination number of \(G\), denoted by \(\gamma_{ev}({ {G}})\), is the minimum cardinality of an \(ev\)-dominating set of \(G\), and any minimum edge-vertex dominating set of \(G\) is referred to as a \(\gamma_{\rm ev}\)-set [17].
Clearly, any matching in a minimum paired-dominating set of a graph \(G\) constitutes an edge-vertex dominating set of \(G\), but not vice versa, that is, all the vertices of edges forming a minimum edge-vertex dominating set of \(G\) do not always constitute a paired-dominating set of \(G\). However, a fundamental, but not common, relation between edge-vertex domination and paired domination was proved by Hedetniemi et al. [15] who established that for any graph \(G\) with no isolated vertex we have \(2\gamma_{\rm ev}({ {G}})=\gamma_{\rm pr}({ {G}})\).
Theorem 1.1. [15] If \(G\) is a graph with no isolated vertex, then \(2\gamma_{\rm ev}({ {G}})=\gamma_{\rm pr}({ {G}})\).
In this short note, we present another one, when restricted to unique dominating set. Namely, a commonly used approach for constructive characterizations of trees with unique minimum dominating sets, for different models of domination [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 16, 19, 23, 21, 22, 24, 25] is to define a set of basic operations such that starting from the initial pre-defined (finite) set of small trees, playing a role of seeds, any tree with the unique minimum dominating set (in the relevant model) can be constructed by applying, successively, a finite sequence of these operations. In particular, Chellali and Haynes [4] characterized the class of trees with unique minimum paired dominating sets by providing the relevant set of four basic graph operations, whereas Senthilkumar et al. [22] – the relevant set of five basic graph operations in the case of edge-vertex domination. However, we establish the following result.
Theorem 1.2. The class of trees having unique minimum edge-vertex dominating sets is equivalent to the class of trees having unique minimum paired dominating sets.
Observe that if a graph \(G\) has a cycle, then uniqueness of a \(\gamma_{\rm pr}\)-set of \(G\) does not imply uniqueness of a \(\gamma_{\rm ev}\)-set of \(G\), see Figure 1 for an example. However, as a side result of the proof of Theorem 1.2, we obtain that such a \( {\gamma_{\rm pr}}\)-uniqueness forces all \(\gamma_{\rm ev}\)-sets of \(G\) to be spanned on the same subset of vertices (Corollary 2.3 and 2.4).
We assume that all graphs are simple, i.e., they contain neither loops nor parallel edges. Recall that the open neighborhood of a vertex \(v\) in a connected graph \({ {G}}= ( {V_{{ {G}}}}, {E_{{ {G}}}})\) is the set \( {N_{{ {G}}}}(v) = \{u \in {V_{{ {G}}}}\colon uv \in {E_{{ {G}}}}\}\), whereas for an edge subset \(M \subseteq {E_{{ {G}}}}\), \( {V_{{ {G}}}}(M)\) denotes the set of vertices of all edges in \(M\). We start with the following crucial lemma (its proof, in general, follows the argument in the proof of Theorem 73 in [18] and Theorem 2.2 in [15], but proceeds with a more detailed analysis).
Lemma 2.1. Let \(D_{\rm ev}\) be a \(\gamma_{\rm ev}\)-set of a graph \({ {G}}=( {V_{{ {G}}}}, {E_{{ {G}}}})\). If there exist two edges in \( {D_{\rm ev}}\) sharing a vertex, then there exist two \((\)distinct\()\) \(\gamma_{\rm ev}\)-sets \( {D_{\rm ev}}'\) and \( {D_{\rm ev}}''\) of \(G\) such that \( {V_{{ {G}}}}( {D_{\rm ev}}') \neq {V_{{ {G}}}}( {D_{\rm ev}}'')\) and no two edges in \( {D_{\rm ev}}'\), resp. \( {D_{\rm ev}}''\), share a vertex.
Proof. Let \(D_{\rm ev}\) be a \(\gamma_{\rm ev}\)-set of a graph \({ {G}}=( {V_{{ {G}}}}, {E_{{ {G}}}})\). We have the following claim (it follows immediately from minimality of \(D_{\rm ev}\)).
Claim. There are no three \((\)distinct\()\) edges in \(D_{\rm ev}\) such that they constitute either a \(4\)-vertex path or a \(3\)-vertex cycle in \(G\).
Assume now that there exist two edges \(e_1,e_2 \in {D_{\rm ev}}\) sharing a vertex, say \(e_1=x_1x_2\) and \(e_2=x_2x_3\). Since \(D_{\rm ev}\) is a \(\gamma_{\rm ev}\)-set, there exists \(x_0 \in {N_{{ {G}}}}(x_1)\) such that \(x_0\) is ev-dominated only by edge \(e_1\), and analogously, there exists \(x_4 \in {N_{{ {G}}}}(x_3)\) such that \(x_4\) is ev-dominated only by edge \(e_2\). Consider now the sets \( {X_{\rm ev}}^1=( {D_{\rm ev}}\setminus\{e_1\}) \cup\{x_0x_1\}\) and \( {Y_{\rm ev}}^1=( {D_{\rm ev}}\setminus\{e_2\}) \cup\{x_3x_4\}\); we shall refer to such edge replacement operation on \(D_{\rm ev}\) as \(D_{\rm ev}\)-twinning. Clearly, \( {X_{\rm ev}}^1\) and \( {Y_{\rm ev}}^1\) are distinct \(\gamma_{\rm ev}\)-sets of \(G\) and \( {X_{\rm ev}}^1 \cap {Y_{\rm ev}}^1 = {D_{\rm ev}}\setminus \{e_1,e_2\}\). Moreover, taking into account the above claim, each of them has less (but the same) number of pairs of edges sharing a vertex. Consequently, if they have no such pair of distinct edges having a vertex in common, we are done.
Otherwise, we focus only on the set \( {X_{\rm ev}}^1\) and apply \( {X_{\rm ev}}^1\)-twinning, which now results in two distinct \(\gamma_{\rm ev}\)-sets \( {X_{\rm ev}}^2\) and \( {Y_{\rm ev}}^2\). We continue (iteratively) \( {X_{\rm ev}}^i\)-twinning procedure as long as \( {X_{\rm ev}}^i\) (and so \( {Y_{\rm ev}}^i\)) has at least one pair of edges sharing a vertex. Eventually, we arrive to the situation when \( {X_{\rm ev}}^i\) (and so \( {Y_{\rm ev}}^i\)) has no two edges having a vertex in common. Clearly, keeping in mind minimality of the initial set \(D_{\rm ev}\), it follows from the construction that the sets \( {X_{\rm ev}}^i\) and \( {Y_{\rm ev}}^i\) are the two sought \( {\gamma_{\rm ev}}\)-sets of \(G\). ◻
Next, let \(G\) be a graph of order at least three (the base case of a \(2\)-vertex tree is obvious) and assume that all \(\gamma_{\rm ev}\)-sets of \(G\) are spanned on the same (unique) vertex set \(D\). Let \(D_{\rm ev}\) be any \(\gamma_{\rm ev}\)-set of \(G\). Taking into account Lemma 2.1, uniqueness of \(D\) implies that no two elements of \(D_{\rm ev}\) share a vertex. Consequently, the set \(D\) of size \(2| {D_{\rm ev}}|\) – perfectly matchable by \(D_{\rm ev}\) – is a minimum paired-dominating set of \(G\) by Theorem 1.1. Furthermore, we claim that \(D\) is unique one. Indeed, suppose to the contrary that there exists another \(\gamma_{\rm pr}\)-set \(D'\) of \(G\). Then, a perfect matching \(M'\) in the induced subgraph \({ {G}}[D']\) is an edge-vertex dominating set of \(G\) with \(|D'|/2=| {D_{\rm ev}}|= {\gamma_{\rm ev}}({ {G}})\), which contradicts uniqueness of \(D\) (since \(D' \neq D\)).
Corollary 2.2. If a graph \(G\) has a unique \(\gamma_{\rm ev}\)-set, then \(G\) has a unique \(\gamma_{\rm pr}\)-set.
Assume now that a graph \(G\) has a unique \(\gamma_{\rm pr}\)-set \(D_{\rm pr}\). We first claim that \(V_{ {G}}( {D_{\rm ev}}')=V_{ {G}}( {D_{\rm ev}}'')\) for any two \(\gamma_{\rm ev}\)-sets of \(G\). Indeed, consider a \(\gamma_{\rm ev}\)-set \(D_{\rm ev}\) of \(G\), with \(2| {D_{\rm ev}}|=| {D_{\rm pr}}|\) (by Theorem 1.1), imposed by a perfect matching in \({ {G}}[ {D_{\rm pr}}]\). It follows from Lemma 2.1 that no two edges in (any) \(\gamma_{\rm ev}\)-set \(D_{\rm ev}\) of \(G\) share a vertex (since otherwise, the relevant sets \(V_{ {G}}( {D_{\rm ev}}')\) and \(V_{ {G}}( {D_{\rm ev}}'')\) in Lemma 2.1 are two distinct \(\gamma_{\rm pr}\)-sets of \(G\), a contradiction with \(D_{\rm pr}\) being unique). So suppose now that \(G\) has two distinct minimum edge-vertex dominating sets, say \( {X_{\rm ev}}'\) and \( {X_{\rm ev}}''\), with no two edges sharing a vertex. If \(V_{ {G}}( {X_{\rm ev}}') \neq V_{ {G}}( {X_{\rm ev}}'')\), then both \(V_{ {G}}( {X_{\rm ev}}')\) and \(V_{ {G}}( {X_{\rm ev}}'')\) are paired-dominating sets of \(G\) of size \( {\gamma_{\rm pr}}({ {G}})\) – a contradiction with uniqueness of \(D_{\rm pr}\). Therefore, we must have \(V_{ {G}}( {X_{\rm ev}}') = V_{ {G}}( {X_{\rm ev}}'')\), which makes us in a position to prove Theorem 1.2.
Observe that if \(V_{ {G}}( {X_{\rm ev}}') = V_{ {G}}( {X_{\rm ev}}'')\), then the induced subgraph \({ {G}}[V_{ {G}}( {X_{\rm ev}}') \cup V_{ {G}}( {X_{\rm ev}}'')]\) has a cycle (since both \( {D_{\rm ev}}'\) and \( {D_{\rm ev}}''\) are perfect matchings in \(G[V_{ {G}}( {X_{\rm ev}}') \cup V_{ {G}}( {D_{\rm ev}}'')]\)), and thus \(G\) is not a tree. Therefore, if \(G\) is a tree, then we must have \( {X_{\rm ev}}'= {X_{\rm ev}}''\), which eventually completes the (simple) proof of Theorem 1.2.
We note in passing that we have actually proved the following two properties.
Corollary 2.3. Let \(T\) be a non-trivial tree. If \(D_{\rm pr}\) is a unique \(\gamma_{\rm pr}\)-set of \(T\), then \(T\) has a unique \(\gamma_{\rm ev}\)-set which is the \((\)unique\()\) perfect matching of \(V_{ {T}}( {D_{\rm ev}})= {D_{\rm pr}}\). Analogously, if \(D_{\rm ev}\) is a unique \(\gamma_{\rm ev}\)-set of \(T\), then \(T\) has a unique \(\gamma_{\rm pr}\)-set which is \(V_{ {T}}( {D_{\rm ev}})\).
Corollary 2.4. Let \(G\) be a simple graph without isolated vertices. Then \(G\) has a unique minimum paired dominating set, say \(D\), if and only if all its minimum edge-vertex dominating sets are spanned on all and only vertices.