Proof. Toward contradiction, if there exist two distinct vertices \(u\) and \(v\) of \(G\) such that \(N(u) \cap C = N(v) \cap C = \emptyset\), then \(C\) does not open-separate the pair \(u,v\), a contradiction. This proves the result. ◻

Proof. It is enough to show that \(C\) open-separates every pair \(u,v\) of distinct vertices of \(G\) such that \(d(u,v) \geq 3\). So, assume that \(u\) and \(v\) are two such vertices of \(G\) with \(d(u,v) \geq 3\). Then, we have \(N(u) \triangle N(v) = N(u) \cup N(v)\). If \(C\) does not open-separate the pair \(u,v\), then it implies that \(C\) does not intersect \(N(u) \cup N(v)\), that is, \(N(u) \cap C = N(v) \cap C = \emptyset\), which contradicts our assumption. Therefore, \(C\) open-separates \(u,v\) and this proves the result. ◻

Proof. Clearly, the set \(S\) is a dominating set of \(G\) since \(S_1\) is a dominating set of \(G_1\). Let \(u,v\) be two distinct vertices of \(G\). Then, we show that the set \(S\) has non-empty intersection with \(N_G(u) \bigtriangleup N_G(v)\). If \(u,v \in V(G_1)\), then we have \(N_G(u) \bigtriangleup N_G(v) = N_{G_1}(u) \bigtriangleup N_{G_1}(v)\). Since \((N_{G_1}(u) \bigtriangleup N_{G_1}(v)) \cap S_1 \ne \emptyset\) due to \(S_1\) being an OD-code of \(G_1\), we have \((N_G(u) \bigtriangleup N_G(v)) \cap S \ne \emptyset\). Now if \(u,v \in V(G_2)\), then \(N_G(u) \bigtriangleup N_G(v) = N_{G_2}(u) \bigtriangleup N_{G_2}(v) \ne \emptyset\) since \(G_2\) is X-admissible. This implies that \((N_{G_2}(u) \bigtriangleup N_{G_2}(v)) \cap V(G_2) \ne \emptyset\) and hence, \((N_G(u) \bigtriangleup N_G(v)) \cap S \ne \emptyset\). Finally, let us assume that \(u \in V(G_1)\) and \(v \in V(G_2)\). Since \(G_2\) is on at least two vertices, this implies that there exists a vertex \(v' \in N_{G_2}(v) \subseteq S\) with \(v' \ne v\). Now, since \(N_G(u) \bigtriangleup N_G(v) = N_{G_1}(u) \cup N_{G_2}(v)\), we have \(v' \in (N_G(u) \cup N_G(v)) \cap S\). This proves the result. ◻

Proof. Let us first prove the result on the lower bound of \(\gamma^{\rm{OD}}(G)\). Let \(S\) be a minimum OD-code of \(G\), that is, \(|S| = \gamma^{\rm{OD}}(G)\). Then, for each vertex \(v \in V(G)\), the subset \(N(v) \cap S \subset S\) is unique. In other words, the number \(n\) of vertices of \(G\) can be at most the number of subsets of \(S\) which is \(2^{|S|}\). This implies that \(\log n \le |S| = \gamma^{\rm{OD}}(G)\) which further implies \(\lceil \log n \rceil \le \gamma^{\rm{OD}}(G)\), since the OD-number is an integer.

We now prove the result on the upper bound of \(\gamma^{\rm{OD}}(G)\). Since \(G\) is without isolated vertices, it must have at least one edge. So, let \(G_1\) be a component of \(G\) with at least one edge and of order \(n_1\). Then, \(G_1\) is also OD-admissible. Let \(G_2\) be the disjoint union of all components of \(G\) other than \(G_1\). In other words, we have \(G = G_1 \oplus G_2\). Let \(S_1\) be a minimum OD-code of \(G_1\), that is, \(|S_1| = \gamma^{\rm{OD}}(G_1)\). Now, if \(\gamma^{\rm{OD}}(G_1) \le n_1-1\), then, by applying Lemma 1, the set \(S = S_1 \cup V(G_2)\) is an OD-code of \(G\). This implies that \(\gamma^{\rm{OD}}(G_1) \le |S| \le n-1\).

Therefore, let us assume that \(\gamma^{\rm{OD}}(G_1) = |S_1| = n_1\), that is, \(S_1 = V(G_1)\). Now, let \(V(G_1)=\{v_1, v_2, \ldots v_{n_1}\}\) and let \(C_i = N(v_i)\) for each \(i \in [n_1]\). Since \(S_1\) is an OD-code of \(G_1\), we have \(C_i \neq C_j\) for all \(i, j \in [n_1]\) and \(i \neq j\). However, by Theorem 1 (Bondy’s theorem), there exists a vertex \(x_1\) of \(G_1\) such that \(C_i \setminus \{x_1\} \neq C_j \setminus \{x_1\}\) for all \(i, j \in [n_1]\) and \(i \neq j\). In other words, the set \(S_1 \setminus \{x_1\}\) is an open-separating set of \(G_1\). Moreover, \(S_1\setminus \{x_1\}\) is also a dominating set of \(G_1\), since \(S_1 \setminus \{x_1\} = V(G_1) \setminus \{x_1\}\) and \(G_1\) is connected. Thus, \(S_1 \setminus \{x_1\}\) is an OD-code of \(G_1\) which is a contradiction to the minimality of \(S_1\) in being an OD-code of \(G_1\). Therefore, we have \(\gamma^{\rm{OD}}(G_1) \leq n_1-1\) and we are again done by Lemma 1. ◻

Proof. Let us first assume that \(G = G' \oplus \{v\}\) for some vertex \(v\) of \(G\). Moreover, let \(C\) be any minimum OD-code of \(G\). Then, \(v \in C\) in order for \(C\) to dominate \(v\). This implies that \(N(v) \cap C = \emptyset\). Therefore, by Remark 1, the set \(C \setminus \{v\}\) must total-dominate all vertices in \(V \setminus \{v\}\), that is, \(C\) is an OD-code of \(G'\). This implies that \(\gamma^{\rm{OTD}}(G') \leq |C| - 1 = \gamma^{\rm{OD}}(G)-1\), that is, \(\gamma^{\rm{OD}}(G) \leq \gamma^{\rm{OTD}}(G') + 1\). On the other hand, if \(C'\) is an OTD-code of \(G'\), then \(C' \cup \{v\}\) is an OD-code of \(G\). This implies that \(\gamma^{\rm{OD}}(G) \leq |C'|+1 = \gamma^{\rm{OTD}}(G')+1\) and hence, assertion (a) follows.

Let us now assume that \(G\) has no isolated vertices. Then, \(G\) is also OTD-admissible. Now, the inequality \(\gamma^{\rm{OD}}(G) \leq \gamma^{\rm{OTD}}(G)\) holds by the fact that any OTD-code of \(G\) is also a dominating and an open-separating set of \(G\) and hence, is an OD-code of \(G\). To prove the other inequality, we let \(C\) be a minimum OD-code  of \(G\). Then, we have \(|C| = \gamma^{\rm{OD}}(G)\). Now, if \(C\) is also an OTD-code of \(G\), then the result holds trivially. Therefore, let us assume that \(C\) is not an OTD-code of \(G\), that is, in particular, \(C\) is not a total-dominating set of \(G\). This implies that there exists a vertex \(v\) of \(G\) such that \(C \cap N(v) = \emptyset\). Moreover, by Remark 1, \(C \cap N(v)=\emptyset\) for exactly the vertex \(v\) of \(G\). This implies that \(C \cup \{v\}\) is a total-dominating set of \(G\) and hence, is also an OTD-code of \(G\). Therefore, we have \(\gamma^{\rm{OTD}}(G) \leq |C|+1 = \gamma^{\rm{OD}}(G) +1\) which implies assertion (b). ◻

Proof. We clearly have, by definition, that every open-separating set of a graph \(G\) is also a locating set of \(G\). Hence, every OD-code of \(G\) is also an LD-code of \(G\) and assertion (a) follows. Moreover, if \(G\) has no isolated vertex, then every OTD-code of \(G\) is also an LTD-code of \(G\) which implies that \(\gamma^{\rm{LTD}}(G) \leq \gamma^{\rm{OTD}}(G)\) holds. Combining the latter inequality with Theorem 3(b), we further conclude \[\gamma^{\rm{LTD}}(G) - 1 \leq \gamma^{\rm{OTD}}(G)- 1 \leq \gamma^{\rm{OD}}(G)\] which implies assertion (b). ◻

Proof. Let \(H\) be the auxiliary graph of SL-SAT. Then \(H\) is bipartite by construction.

Each vertex of \(H\) corresponding to the literals from \(X\) has degree \(2\) (since a literal belongs to at most two clauses); and each vertex of \(H\) corresponding to the clauses in \(\mathcal{C}\) has degree at most \(3\) (since each clause contains at most \(3\) literals). This proves the result on the maximum degree of \(H\).

Finally, \(H\) cannot contain an induced four-cycle as it would imply that there exist two clauses having two literals in common which contradicts the input constraint of SL-SAT. Moreover, since \(H\) is bipartite and hence, contains only even cycles, all induced cycles in \(H\) must be of length at least \(6\). This proves the result on the girth of \(H\). ◻

Proof. Clearly, SL-SAT belongs to the class NP. Let \(X' = X \cup Y\) and \(\phi' = \phi \wedge \mu\), where \(Y\) is the set of auxiliary variables introduced in Reduction 1 and \(\mu\) is the Boolean formula obtained by appending the clauses in Reduction 1. Note that \(\phi\) has literals only from \(X\).

To prove the necessary part of the NP-hardness, let \(\psi = (X, \mathcal{C})\) be a Yes-instance of LSAT and so, let \(A : X \to \{0,1\}\) be a satisfying assignment on \(X\). Then, we create an assignment \(A' : X' \to \{0,1\}\) by requiring \(A'(x) = A(x)\) if \(x \in X\) and \(A'(x) = 1\) if \(x \in Y\). Then it is clear that this is a satisfying assignment on \(X'\) since \(\phi' = \phi \wedge \mu\) and each clause in \(\mu\) has an auxiliay variable which is assigned to \(1\) by \(A'\). Hence, \(\psi' = (X', \mathcal{C}')\) is a Yes-instance of SL-SAT.

To prove the sufficiency part of the NP-hardness, if \(\psi'\) is a Yes-instance of SL-SAT and \(A' : X' \to \{0,1\}\) is a satisfying assignment on \(X'\), we create an assignment of \(A : X \to \{0,1\}\) by requiring \(A(x) = A'(x)\). Again, \(\phi' = \phi \wedge \mu\) implies that \(A\) is a satisfying assignment on \(X\). Hence, \(\psi\) is a Yes-instance of LSAT. ◻

Proof. (1) Let \(S\) be an OTD-code of \(G^\psi\). Then, for each \((v_1,v_2,v_3) \in T\), the vertex \(v_2\) must belong to \(S\) for the latter to total-dominate \(v_3\). Moreover, at least one vertex from the pair \((v_1,v_3)\) must be in \(S\) for the latter to total-dominate the vertex \(v_2\). In total therefore, counting over all the \(n\) variable gadgets and \(m\) clause gadgets, we have \(|T \cap S| \geq 2n+2m\).

(2) Let \(S\) be an OD-code of \(G^\psi\). Now, if at least two vertices out of each triple \((t_1,t_2,t_3) \in T\) belong to \(S\), then we have \(|S| \geq 2n+2m > 2n+2m-1\) and thus, we are done. So, let us assume that there exists one triple \((t^\star_1,t^\star_2,t^\star_3) \in T\) which has at most one vertex in \(S\). However, every triple \((t_1,t_2,t_3) \in T\) must have at least one of \(t_2\) and \(t_3\) in \(S\) in order for the latter to dominate \(t_3\). This implies that exactly one of \(t^\star_2\) and \(t^\star_3\) belongs to \(S\). This further implies that either \(N_{G^\psi}(t^\star_2) \cap S = \emptyset\) or \(N_{G^\psi}(t^\star_3) \cap S = \emptyset\). This further implies that each triple of \(T\) other than \((t^\star_1,t^\star_2,t^\star_3)\) has at least two vertices in \(S\) (or else, two vertices of \(G^\psi\) would have empty neighborhoods in \(S\) and hence, the pair would not be open-separated by \(S\), a contradiction). Thus, again counting over all the \(n\) variable gadgets and \(m\) clause gadgets, we have \(|S| \geq 2n+2m-1\).

Finally, in each of the above two cases, since \(S\) is an open-separating set of \(G^\psi\), at least one of \(w^x_1\) and \(w^x_2\) must be in \(S\) in order for the latter to open-separate the pair \(v^x_1, v^x_3\). This implies the final statement of the result. ◻

Proof. Let \(x_0 \in X\) be any fixed variable. We now look at the two cases.

(1) Since \(\gamma^{\rm{OD}}(G^\psi) \geq 3n+2m-1\) by Lemma 3, in order to prove that \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\), it is enough to show the existence of an OD-code of \(G^\psi\) of order at most \(3n+2m-1\). Let us now construct a code \(S\) of \(G^\psi\) by including in it the following vertices.

1. \(v^x_1\) for all \(x \in X \setminus \{x_0\}\) and \(v^x_2\) for all \(x \in X\).

2. \(u^\mathbf{c}_1,u^\mathbf{c}_2\) for all \(\mathbf{c} \in \mathcal{C}\).

3. For some \(x \in X\), if exactly one of \(x\) and \(\neg x\) appears in the formula \(\phi\), say \(x\), then we pick \(w^x_1\) in \(S\), or else, we pick \(w^x_2\) in \(S\).

4. If for some variable \(x \in X\), both the literals \(x\) and \(\neg x\) belong to some respective clauses, say \(\boldsymbol{c}\) and \(\mathbf{c}'\), then exactly one of the literals is assigned \(1\) in the satisfying assignment on \(X\). If \(x\) is assigned \(1\), we pick \(w^x_1\) in \(S\), or else, we pick \(w^x_2\) in \(S\).

This implies that every variable gadget has either \(w^x_1\) or \(w^x_2\) (but not both) in \(S\) and hence, \(|S| = 3n+2m-1\). We now show that \(S\) is an OD-code of \(G^\psi\). To start with, we observe that \(S\) is a dominating set of \(G^\psi\). Thus, it is left to show that \(S\) is also an open-separating set of \(G\). We also observe that for exactly the one vertex \(v^{x_0}_2\) of \(G^\psi\), we have \(N(v^{x_0}_2) \cap S = \emptyset\). Hence, to prove that \(S\), indeed, is an open-separating set of \(G^\psi\), by Remark 2, it is enough to check that all pairs of vertices of \(G^\psi\) of distance at most two between them are open-separated by \(S\). We show next that this is true. Let \(x \in X\) and \(\boldsymbol{c} \in \mathcal{C}\) be any general Boolean variable and clause, respectively.

• Since \(N(v^{x_0}_2) \cap S = \emptyset\) uniquely, therefore, \(S\) open-separates \(v^{x_0}_2\) from every other vertex of \(G^\psi\).

• The vertex \(v^x_2\) open-separates \(v^x_3\) from every vertex of \(G^\psi\) except \(v^x_1\). However, the vertices \(v^x_1, v^x_3\) are open-separated by whichever of \(w^x_1\) and \(w^x_2\) is in \(S\).

• Similarly, the vertex \(u^\mathbf{c}_2\) open-separates \(u^\mathbf{c}_3\) from every vertex of \(G^\psi\) except \(u^\mathbf{c}_1\). However, the clause \(\mathbf{c}\) has a literal, say \(x\) or \(\neg x'\), which is assigned \(1\) in the satisfying assignment on \(X\). Then, the vertices \(u^\mathbf{c}_1, u^\mathbf{c}_3\) are open-separated by \(w^x_1\) if \(x\) is assigned \(1\) or by \(w^x_2\) if \(\neg x'\) is assigned \(1\).

• Every vertex of \(G^\psi\) in \(S\) open-separates itself from all its neighbors. Therefore, we now check that each vertex in \(S\) is also open-separated by \(S\) from all other vertices at distance \(2\) from the former.

• The vertex \(v^x_2\) open-separates \(v^x_1\) from every vertex of \(G^\psi\) except \(v^x_3\). However, the pair \(v^x_1, v^x_3\) were previously shown to be open-separated by \(S\).

• Similarly, the vertex \(u^\mathbf{c}_2\) open-separates \(u^\mathbf{c}_1\) from every vertex of \(G^\psi\) except \(u^\mathbf{c}_3\). Once again, the pair \(u^\mathbf{c}_1, u^\mathbf{c}_3\) was already shown to be open-separated by \(S\).

• We now look at the open-separation of the pair \(v^x_2, w^x_i\) by \(S\), where \(i \in [2]\). Let us assume, without loss of generality, that the vertex \(w^x_1\) exists in the graph \(G^\psi\). Then, \(w^x_1\) has a neighbor \(u^\mathbf{c}_1\) for some clause \(\mathbf{c} \in \mathcal{C}\). Then, we have \(w^x_1 u^\mathbf{c}_1 \in E(G^\psi)\). Since \(u^\mathbf{c}_1 \in S\), the pair \(v^x_2, w^x_1\) is open-separated by \(u^\mathbf{c}_1 \in S\). The case for the open-separation of the pair \(v^x_2, w^x_2\) (if \(w^x_2\) exists in \(G^\psi\)) by \(S\) follows by exactly the same reasoning.

• We now look at the open-separation by \(S\) of the vertex \(u^\mathbf{c}_2\) from other vertices (of distance \(2\)) from it. Let \(x \in X\) be such that \(x\) has a literal in \(\mathbf{c}\). Without loss of generality, let \(x\) itself be a literal in \(\mathbf{c}\). Thus, we look at the pair \(w^x_1, u^\mathbf{c}_2\) to be open-separated by \(S\). Since the literal \(x\) appears in two clauses, say \(\mathbf{c}\) and \(\mathbf{c}'\), we have the edges \(w^x_1 u^\mathbf{c}_1 \in E(G^\psi)\) and \(w^x_1 u^{\mathbf{c}'}_1 \in E(G^\psi)\). This implies that the vertices \(w^x_1, u^\mathbf{c}_2\) are open-separated by \(u^{\mathbf{c}'}_1\). Similarly, the vertices \(w^x_1, u^{\mathbf{c}'}_2\) are open-separated by \(u^\mathbf{c}_1\) (this is where we use the property of saturating an LSAT formula so that the literal \(x\) appears in two clauses. Otherwise, if \(x_0\) belongs to the clause \(\mathbf{c_0}\), the pair \(u^{\mathbf{c_0}}_2, w^{x_0}_1\) would not be open-separated by \(S\) since \(v^{x_0}_1, u^{\mathbf{c_0}}_3 \notin S\)).

Finally, the only vertices in different variable gadgets (respectively, clause gadgets) with distance 2 between them are of the form \(w^x_i \in G^x\) and \(w^{x'}_j \in G^{x'}\) (respectively, \(u^\mathbf{c}_1 \in P^\mathbf{c}\) and \(u^{\mathbf{c}'}_1 \in P^{\mathbf{c}'}\)), where \(x,x' \in X\) (respectively, \(\mathbf{c},\mathbf{c}' \in \mathcal{C}\)) are distinct. However, the set \(S\) open-separates any such pair \(w^x_i, w^{x'}_j\) by either \(v^x_1\) (if \(x_1 \ne x_0\)) or by \(v^{x'}_1\) (if \(x'_1 \ne x_0\)); and the pair \(u^\mathbf{c}_1, u^{\mathbf{c}'}_1\) by \(u^\mathbf{c}_2\). This proves that \(S\) is an open-separating set of \(G^\psi\).
(2) Again, by Lemma 3, we have \(\gamma^{\rm{OTD}}(G^\psi) \geq 3n+2m\). Therefore, to show that \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\), it is enough to show that there exists an OTD-code of \(G^\psi\) of order at most \(3n+2m\). To that end, we simply replace the OD-code \(S\) constructed above in part (1) by \(S' = S \cup \{v^{x_0}_1\}\) which then becomes a total-dominating set of \(G^\psi\). Moreover, since adding vertices to an open-separating set keeps it open-separating, \(S'\) is also an open-separating set of \(G^\psi\). Moreover, \(|S'| = |S| + 1 = 3n+2m\). This proves the lemma. ◻

Proof. Let \(S\) be an open-separating set of \(G^\psi\) such that \(|\{w^x_1,w^x_2\} \cap S| = 1\) for all \(x \in X\). We now provide a binary assignment on \(X\) the following way: for any \(x \in X\), if \(w^x_1 \in S\) and \(w^x_2 \notin S\), then put \((x,\neg x)= (1,0)\); and if \(w^x_1 \notin S\) and \(w^x_2 \in S\), then put \((x,\neg x) = (0,1)\). Clearly, this assignment on \(X\) is a valid one since, for each \(x \in X\), exactly one of \(x\) and \(\neg x\) is assigned \(1\) and the other \(0\). To now prove that this assignment on \(X\) is also a satisfying one, we simply note that, for each clause \(\mathbf{c} \in \mathcal{C}\), in order for the set \(S\) to open-separate \(u^\mathbf{c}_1\) and \(u^\mathbf{c}_3\), either there exists a variable \(x \in X\) such that \(u^\mathbf{c}_1w^x_1 \in E(G^\psi)\) with \(w^x_1 \in S\); or there exists a variable \(x' \in X\) such that \(u^\mathbf{c}_1w^{x'}_2 \in E(G^\psi)\) and \(w^{x'}_2 \in S\). Therefore, by construction of the graph \(G^\psi\), either \(x\) is a variable in the clause \(\mathbf{c}\) with \((x,\neg x) = (1,0)\) or \(x'\) is a variable whose literal \(\neg x'\) is in the clause \(\mathbf{c}\) with \((x', \neg x') = (0,1)\). Hence, the binary assignment formulated on \(X\) is a satisfying one. ◻

Proof. Let \(S\) be either an OD-code or an OTD-code of \(G^\psi\). Since \(S\) open-separates the vertices \(v^w_1, v^x_3\), it implies that at least one of \(w^x_1\) and \(w^x_2\) must be in \(S\). Then, by Lemma 5, to show that \(X\) has a valid satisfying assignment, it is enough to show that \(|\{w^x_1, w^x_2\} \cap S| = 1\).

Let us first assume that \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\) and let \(S'\) be an OD-code of \(G^\psi\) such that \(|S'| = 3n+2m-1\). If on the contrary, there exists some variable \(x' \in X\) for which \(|\{w^x_1, w^x_2\} \cap S'| = 2\), then using Lemma 3(1), we have \[\begin{align} 3n+2m-1 = |S'| &= |T \cap S'| + |\{w^{x'}_1, w^{x'}_2\} \cap S'| + \sum_{x \in X \setminus \{x'\}} |\{w^x_1, w^x_2\} \cap S'| \ge 3n+2m. \end{align}\] which is a contradiction. Therefore, \(|\{w^{x'}_1, w^{x'}_2\} \cap S'| = 1\) and this proves (1).

Let us now assume that \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\) and let \(S\) be an OTD-code of \(G^\psi\) such that \(|S| = 3n+2m\). Again, if on the contrary, there exists some variable \(x' \in X\) for which \(|\{w^{x'}_1, w^{x'}_2\} \cap S| = 2\), then using Lemma 3(2), we have \[\begin{align} 3n+2m = |S| &= |T \cap S| + |\{w^{x'}_1, w^{x'}_2\} \cap S| + \sum_{x \in X \setminus \{x'\}} |\{w^x_1, w^x_2\} \cap S| \ge 3n+2m+1. \end{align}\] which is again a contradiction. Therefore, \(|\{w^{x'}_1, w^{x'}_2\} \cap S| = 1\) and this proves (2). ◻

Proof. Let \(V_1 = \{u^\mathbf{c}_1, u^\mathbf{c}_3, v^x_1, v^x_3 : x \in X, \mathbf{c} \in \mathcal{C}\}\) and \(V_2 = \{u^\mathbf{c}_2, w^x_1, w^x_2, v^x_2 : x \in X, \mathbf{c} \in \mathcal{C}\}\). Then it can be checked that the sets \(V_1\) and \(V_2\) are each independent sets. Moreover, \(V(G^\psi) = V_1 \cup V_2\). This implies that \(G^\psi\) is a bipartite graph.

All vertices in \(\{u^\mathbf{c}_2, u^\mathbf{c}_3, v^x_2, v^x_3\}\) have degree at most \(3\) and the vertex \(v^x_1\) is of degree \(3\). Since each literal from \(X\) can appear in at most two clauses, it implies that the degrees of the vertices \(w^x_1\) and \(w^x_2\) are at mos \(3\). Finally, every clause \(\mathbf{c} \in \mathcal{C}\) has at most \(3\) literals from \(X\). This implies that the vertex \(u^\mathbf{c}_1\) is of degree at most \(4\). This proves that the graph \(G^\psi\) is of maximum degree \(4\).

Notice that any induced cycle of \(G^\psi\) must include vertices only in the set \(S = \{u^{\mathbf{c}}_1 : \mathbf{c} \in \mathcal{C}\} \cup \{v^x_1, w^x_1, w^x_2 : x \in X\}\). Also, let \(S' = \{u^{\mathbf{c}}_1 : \mathbf{c} \in \mathcal{C}\} \cup \{w^x_1, w^x_2 : x \in X\}\). Then \(G^\psi[S']\) is isomorphic to the auxiliary graph of SL-SAT. Therefore, by Remark 3, any cycle of \(G^\psi\) induced only by the vertices of \(S'\) must be of length at least \(6\). Moreover, any cycle of \(G^\psi\) with a vertex in \(\{v^x_1 : x \in X\}\) must also include the vertices \(w^x_1\) and \(w^x_2\) with \(G^\psi[v^x_1, w^x_1, w^x_3]\) being isomorphic to \(P_3\). Since the latter two vertices are not adjacent to a common \(u^{\mathbf{c}}_1\) (or else, both literals of a variable would appear in the same clause), the cycle must be of length at least \(6\). Hence, this proves that all induced cycles of \(G^\psi\) are of length at least \(6\). Therefore, the graph \(G^\psi\) is of girth at least \(6\). ◻

Proof. OD-Code clearly belongs to the class NPsince it can be verified in polynomial-time if a given vertex subset of a graph \(G\) is an OD-code of \(G\). To prove NP-hardness, we show that an instance \(\psi=(X,\mathcal{C})\) with \(|X|=n\) and \(|\mathcal{C}|=m\) is a Yes-instance of SL-SAT if and only if \((G^\psi,3n+2m-1)\) is a Yes-instance of OD-Code, where the graph \(G^\psi\) is as constructed in Reduction 2. In other words, we show that \(X\) has a satisfying assignment if and only if there exists an OD-code \(S\) of \(G^\psi\) such that \(|S| \leq 3n+2m-1\).

To prove the necessary part of the last statement, if \(X\) has a satisfying assignment, then by Lemma 4(1), we have \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\). This implies that there exists an OD-code \(S\) of \(G^\psi\) such that \(|S| = 3n+2m-1\). On the other hand, to prove the sufficiency, if there exists an OD-code \(S\) of \(G^\psi\) such that \(|S| \le 3n+2m-1\), then combining with Lemma 3, we have \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\). Therefore, by Lemma 6(1), there exists a satisfying assignment on \(X\).

Finally, by Lemma 7, the graph \(G^\psi\) is bipartite and of maximum degree \(4\) and girth at least \(6\). This proves the result. ◻

Proof. We show that OTD= OD+1 is NP-hard by showing that an instance \(\psi=(X,\mathcal{C})\) with \(|X|=n\) and \(|\mathcal{C}|=m\) is a Yes-instance of SL-SAT if and only if \((G^\psi, 3n+2m)\) is a Yes-instance of OTD= OD+1, where the graph \(G^\psi\) is as constructed in Reduction 2. In other words, we show that \(X\) has a satisfying assignment if and only if \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\) and \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\).

The necessary condition is true since, if \(X\) has a satisfying assignment, then by Lemma 4, we have \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\) and \(\gamma^{\rm{OD}}(G^\psi) = 3m+2m-1\). To prove the sufficiency condition, let us assume that \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\) and \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m-1\). Then, by Lemma 6, \(X\) has a satisfying assignment.

Finally, by Lemma 7, the graph \(G^\psi\) is bipartite and of maximum degree \(4\) and girth at least \(6\). This proves the result. ◻

Proof. OTD-Code clearly belongs to the class NPsince it can be verified in polynomial-time if a given vertex subset of a graph \(G\) is an OTD-code of \(G\). To prove NP-hardness, we show that an instance \(\psi=(X,\mathcal{C})\) with \(|X|=n\) and \(|\mathcal{C}|=m\) is a Yes-instance of SL-SAT if and only if \((G^\psi,3n+2m)\) is a Yes-instance of OTD-Code, where the graph \(G^\psi\) is as constructed in Reduction 2. In other words, we show that \(X\) has a satisfying assignment if and only if there exists an OTD-code \(S\) of \(G^\psi\) such that \(|S| \leq 3n+2m\).

To prove the necessary part of the last statement, if \(X\) has a satisfying assignment, then by Lemma 4(2), we have \(\gamma^{\rm{OD}}(G^\psi) = 3n+2m\). This implies that there exists an OTD-code \(S\) of \(G^\psi\) such that \(|S| = 3n+2m\). On the other hand, to prove the sufficiency, if there exists an OTD-code \(S\) of \(G^\psi\) such that \(|S| \le 3n+2m\), then combining with Lemma 3, we have \(\gamma^{\rm{OTD}}(G^\psi) = 3n+2m\). Therefore, by Lemma 6(2), there exists a satisfying assignment on \(X\).

Finally, by Lemma 7, the graph \(G^\psi\) is bipartite and of maximum degree \(4\) and girth at least \(6\). This proves the result. ◻

Proof. Consider a clique \(K_n = (V, V \times V)\) with \(n \geq 2\). \(\mathcal{H}_{{\mathrm{\small OD}}}(K_n)\) is clearly composed of

• the closed neighborhoods \(N[v]=V\) of all vertices \(v \in V\) and

• the symmetric differences \(\Delta(u,v)= \{u,v\}\) of open neighborhoods of distinct vertices \(u,v \in V\).

This shows that all neighborhoods are redundant. Thus, \(\mathcal{C}_{{\mathrm{\small OD}}}(K_n) = {\cal{R}}_n^2 = K_n\) follows which implies \(\gamma^{\rm{OD}}(K_n) = \tau({\cal{R}}_n^2) = n-1\) by [31]. ◻

Proof. Consider the disjoint union \(G = K_{n_1} \oplus \ldots \oplus K_{n_k}\) of cliques with \(1 < n_1 \leq \ldots \leq n_k\) and \(k \geq 2\) and suppose that \(n_i = 2\) for all \(i \leq \ell \leq k\) (with possibly \(0 = \ell\), that is all \(n_i \geq 3\)). Let us further denote \(V_i = V(K_{n_i})\). Then, \(\mathcal{H}_{{\mathrm{\small OD}}}(G)\) is clearly composed of

• the closed neighborhoods \(N[v]=V_i\) of all vertices \(v \in V_i\), \(1 \leq i \leq k\) and

• the symmetric differences \(\Delta(u,v)= \{u,v\}\) of distinct vertices \(u,v \in V_i\) as well as \(\Delta(u,v)= N(u) \cup N(v)\) for \(v \in V_i\), \(u \in V_j\) with \(i \neq j\).

This shows that all neighborhoods are redundant (by \(1 < n_1\)), as well as all symmetric differences of open neighborhoods of vertices from different components \(K_{n_i}\) and \(K_{n_j}\) as soon as at least one of \(n_i\) and \(n_j\) is \(\ge 3\). This implies \(\mathcal{C}_{{\mathrm{\small OD}}}(G) = K_{2\ell} \oplus K_{n_{\ell+1}} \oplus \ldots + K_{n_k}\) and, accordingly, \(\gamma^{\rm{OD}}(G) = (2\ell-1) + \sum_{\ell < i \leq k} (n_i-1)\) follows by [31]. ◻

Proof. Consider such a \(k\)-clique-star \(S_k\) for some \(k \geq 2\) and let \(V = \{u\} \cup \bigcup_{1 \leq i \leq k} V_i\) where \(u\) is the universal vertex and \(V_i\) denotes the vertex subset of \(K_{n_i}\). Furthermore, let \(W_2 = \bigcup_{n_i = 2} V_i\). In order to determine \(\mathcal{C}_{{\mathrm{\small X}}}(S_k)\) and \(\gamma^{\rm{X}}(S_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\), we first construct the X-hypergraphs. Recall that the following hyperedges are involved: the closed or open neighborhoods

• \(N[v]=V_i \cup \{u\}\) and \(N(v) = (V_i\setminus \{v\}) \cup \{u\}\) of all vertices \(v \in V_i\), \(1 \leq i \leq k\) and

• \(N[u]=V\) and \(N(u) = V \setminus \{u\}\)

and the symmetric differences of open neighborhoods of distinct vertices

• \(\Delta(u,v)= (V \setminus V_i) \cup \{v\}\) for all \(v \in V_i\), \(1 \leq i \leq k\),

• \(\Delta(v,v')= \{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\) and \(1 \leq i \leq k\), \(n_i \geq 2\),

• \(\Delta(v,w)= (V_i\setminus \{v\}) \cup (V_j\setminus \{w\})\) for all \(v \in V_i\), \(w \in V_j\) and \(1 \leq i < j \leq k\).

• If \(n_1 = 1\) and \(n_2 = \ldots = n_{\ell} = 2\) holds for some \(\ell \leq k\), then \(\Delta(v_1,w)= (\emptyset \cup (V_j\setminus \{w\}) = \{w'\}\) follows for \(\{v_1\} = V_1\) and all \(w \in V_j = \{w,w'\}\), \(1 < j \leq \ell\). This implies \(W_2 \subseteq \mathcal{F}^1_{\mathrm{\small X}}(S_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\) and shows together with

  • \(N[v_1]=\{v_1,u\}\) and \(N(v_1) =\{u\}\),

  • \(\Delta(v,v')= \{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\) and \(\ell + 1 \leq i \leq k\)

  that all other hyperedges are redundant.

  We conclude that the OD-clutter is composed of \(W_2\), \(\{v_1,u\}\), and \(\{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\) and \(\ell+1 \leq i \leq k\), hence \(\mathcal{C}_{{\mathrm{\small OD}}}(S_k) = K_2 \oplus 2(\ell-1)K_1 \oplus \sum_{n_i\geq 3} K_{n_i}\), whereas the OTD-clutter is composed of \(W_2\), \(\{u\}\), and \(\{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\) and \(\ell+1 \leq i \leq k\), and hence \(\mathcal{C}_{{\mathrm{\small OTD}}}(S_k) = (2\ell-1)K_1 \oplus \sum_{n_i\geq 3} K_{n_i}\) (note that \(V^0_{{\mathrm{\small OTD}}}(S_k) = \{v_1\}\)).

  In both cases, this implies \(\gamma^{\rm{OD}}(S_k) = \gamma^{\rm{OTD}}(S_k) = 2\ell-1 + \sum_{n_i\geq 3} (n_i-1)\).

• If \(n_1 = \ldots = n_{\ell} = 2\) for some \(1 \leq \ell \leq k\), then we see that the OD-clutter is composed of

  • \(\Delta(v,v')= \{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\), \(1 \leq i \leq k\),

  • \(\Delta(v,w)= (V_i\setminus \{v\}) \cup (V_j\setminus \{w\})\) for all \(v \in V_i\), \(w \in V_j\) and \(1 \leq i < j \leq \ell\),

  whereas all neighborhoods and all other symmetric differences are redundant and \(V^0_{{\mathrm{\small OD}}}(S_k) = \{u\}\). This implies \(\mathcal{C}_{{\mathrm{\small OD}}}(S_k) = K_{2\ell} \oplus \sum_{n_i\geq 3} K_{n_i}\), where \(K_{2\ell}\) is composed of the vertices in \(W_2\), and \(\gamma^{\rm{OD}}(S_k) = 2\ell-1 + \sum_{n_i\geq 3} (n_i-1)\).

  On the other hand, the OTD-clutter is composed of all hyperedges of \(\mathcal{C}_{{\mathrm{\small OD}}}(S_k)\) together with \(N(v) = \{v',u\}\) of all vertices \(v \in V_i = \{v',v\}\) and \(1 \leq i \leq \ell\), whereas all other neighborhoods and symmetric differences are redundant. This implies \(\mathcal{C}_{{\mathrm{\small OTD}}}(S_k) = K_{2\ell+1} \oplus \sum_{n_i\geq 3} K_{n_i}\), where \(K_{2\ell+1}\) is composed of the vertices in \(W_2 \cup \{u\}\), and \(\gamma^{\rm{OTD}}(S_k) = 2\ell + \sum_{n_i\geq 3} (n_i-1)\).

• If \(n_1\geq 3\), then we see that both clutters only contain \(\Delta(v,v')= \{v,v'\}\) for all \(v,v' \in V_i\) with \(v \neq v'\), \(1 \leq i \leq k\) as hyperedges since all neighborhoods and all other symmetric differences are redundant. Moreover, we have \(V_{\mathrm{\small OD}}^0 (S_k) = V_{\mathrm{\small OTD}}^0 (S_k) = \{u\}\). This finally implies \(\mathcal{C}_{{\mathrm{\small OD}}}(S_k) = \mathcal{C}_{{\mathrm{\small OTD}}}(S_k) = \sum_{1 \leq i \leq k} K_{n_i}\) and \(\gamma^{\rm{OD}}(S_k) = \gamma^{\rm{OTD}}(S_k) = \sum_{1 \leq i \leq k} (n_i-1)\) follows.

 ◻

Proof. Consider a half-graph \(B_k=(U \cup W, E)\) with its stable vertex sets \(U = \{u_1, \ldots , u_k\}\) and \(W = \{w_1, \ldots , w_k \}\) and edges \(u_iw_j\) if and only if \(i \leq j\) for some \(k \geq 2\). In order to determine \(\mathcal{C}_{{\mathrm{\small X}}}(B_k)\) and \(\gamma^{\rm{X}}(B_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\), we first construct the X-hypergraphs. Recall that the following hyperedges are involved: the closed or open neighborhoods

• \(N[u_i] = \{u_i\} \cup \{w_i, \ldots, w_k\}\) and \(N(u_i) = \{w_i, \ldots, w_k\}\) for \(1 \leq i \leq k\),

• \(N[w_j] = \{u_1, \ldots , u_j\} \cup \{w_j\}\) and \(N(w_j) = \{u_1, \ldots , u_j\}\) for \(1 \leq j \leq k\),

and the symmetric differences of open neighborhoods of distinct vertices

• \(\Delta(u_i,u_j) = \{w_i, \ldots, w_{j-1}\}\) for \(1 \leq i < j \leq k\),

• \(\Delta(u_i,w_j) = \{w_i, \ldots, w_k\} \cup \{u_1, \ldots , u_j\}\) for \(1 \leq i,j \leq k\),

• \(\Delta(w_i,w_j) = \{u_{1+1}, \ldots , u_j\}\) for \(1 \leq i < j \leq k\).

In particular, we see that

• \(\Delta(u_i,u_{1+1}) = \{w_i\}\) for \(1 \leq i < k\),

• \(\Delta(w_i,w_{1+1}) = \{u_{1+1}\}\) for \(1 \leq i < k\)

belong to \(\mathcal{F}^1_{{\mathrm{\small X}}}(B_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\). Noting further that \(N(u_k) = \{w_k\}\) and \(N(w_1) = \{u_1\}\) holds implies \(\mathcal{F}^1_{{\mathrm{\small OTD}}}(B_k) = U \cup W\) and thus \(\mathcal{C}_{{\mathrm{\small OTD}}}(B_k) = 2kK_1\) and \(\gamma^{\rm{OTD}}(B_k) = 2k\). On the other hand, it is easy to see that \(\Delta(u_k,w_1) = \{w_k,u_1\}\) is the only hyperedge in \(\mathcal{F}^2_{{\mathrm{\small OD}}}(B_k)\), thus \(\mathcal{C}_{{\mathrm{\small OD}}}(B_k) = (2k-2)K_1 \oplus K_{2}\) and \(\gamma^{\rm{OD}}(B_k) = 2k-1\) follows. ◻

Proof. Consider a \(k\)-double star \(D_k=(U \cup W, E)\) with vertex sets \(U = \{u_0,u_1, \ldots , u_k\}\) and \(W = \{w_1, \ldots , w_k \}\) and edges \(u_i w_i\) and \(u_0 w_i\) for all \(w_i \in W\) for some \(k \geq 3\). In order to determine \(\mathcal{C}_{{\mathrm{\small X}}}(D_k)\) and \(\gamma^{\rm{X}}(D_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\), we first construct the X-hypergraphs. Recall that the following hyperedges are involved: the closed or open neighborhoods

• \(N[u_0] = \{u_0\} \cup W\) and \(N(u_0) = W\),

• \(N[u_i] = \{u_i,w_i\}\) and \(N(u_i) = \{w_i\}\) for \(1 \leq i \leq k\),

• \(N[w_i] = \{u_0,u_i,w_i\}\) and \(N(w_i) = \{u_0,u_i\}\) for \(1 \leq i \leq k\),

and the symmetric differences of open neighborhoods of distinct vertices

• \(\Delta(u_0,u_i) = W \setminus \{w_i\}\) for \(1 \leq i \leq k\),

• \(\Delta(u_0,w_i) = W \cup \{u_0,u_i\}\) for \(1 \leq i \leq k\),

• \(\Delta(u_i,u_j) = \{w_i,w_j\}\) for \(1 \leq i < j \leq k\),

• \(\Delta(u_i,w_j) = \{u_0,u_j,w_i\}\) for \(1 \leq i,j \leq k\),

• \(\Delta(w_i,w_j) = \{u_i,u_j\}\) for \(1 \leq i < j \leq k\).

The OD-hypergraph involves the closed neighborhoods and all symmetric differences, including

• \(N[u_i] = \{u_i,w_i\}\) for \(1 \leq i \leq k\),

• \(\Delta(u_i,u_j) = \{w_i,w_j\}\) for \(1 \leq i < j \leq k\),

• \(\Delta(u_i,w_j) = \{u_0,u_j,w_i\}\) for \(1 \leq i,j \leq k\) for \(i \neq j\),

• \(\Delta(w_i,w_j) = \{u_i,u_j\}\) for \(1 \leq i < j \leq k\),

which implies that all other hyperedges are redundant for any \(k \geq 3\). Analyzing the hyperedges remaining in \(\mathcal{C}_{{\mathrm{\small OD}}}(D_k)\) shows that \((U \setminus \{u_i\}) \cup (W \setminus \{w_j\})\) for \(0 \leq i \leq k\), \(1 \leq j \leq k\) and \(i \neq j\) as well as \((U \setminus \{u_0,u_i\}) \cup W\) for \(1 \leq i \leq k\) are the only minimum OD-codes of \(D_k\) and thus \(\gamma^{\rm{OD}}(D_k) = 2k-1\) follows.

The OTD-hypergraph involves the open neighborhoods and all symmetric differences, including

• \(N(u_i) = \{w_i\}\) for \(1 \leq i \leq k\),

• \(N(w_i) = \{u_0,u_i\}\) for \(1 \leq i \leq k\),

• \(\Delta(w_i,w_j) = \{u_i,u_j\}\) for \(1 \leq i < j \leq k\),

which implies that all other hyperedges are redundant for any \(k \geq 3\). Analyzing the hyperedges remaining in \(\mathcal{C}_{{\mathrm{\small OTD}}}(D_k) = kK_1 \oplus K_{k+1}\) shows that \((U \setminus \{u_i\}) \cup W\) for \(0 \leq i \leq k\) are the only minimum OTD-codes of \(D_k\) and \(\gamma^{\rm{OTD}}(D_k) = 2k\) holds. ◻

Proof. Consider a thick headless spider \(\overline{H}_k=(Q \cup S, E)\) with \(k \geq 3\). \(\mathcal{H}_{{\mathrm{\small OD}}}(\overline{H}_k)\) is composed of the closed neighborhoods

• \(N[s_i] = Q \setminus \{q_i\} \cup \{s_i\}\) for all \(s_i \in S\),

• \(N[q_i] = Q \cup \{s_i\}\) for all \(q_i \in Q\)

and the symmetric differences

• \(\Delta(s_i,s_j) = \{q_i,q_j\}\) for all distinct \(s_i,s_j \in S\),

• \(\Delta(q_i,q_j) = \{q_i,q_j\} \cup \{s_i,s_j\}\) for all distinct \(q_i,q_j \in C\),

• \(\Delta(q_i,s_j) = \begin{cases} S \setminus \{s_i\}, &if i=j; \\ \{q_i,q_j\} \cup S \setminus \{s_i\}, &if i \neq j.\\ \end{cases}\)

This shows that all neighborhoods are redundant as well as all \(\Delta(q_i,q_j)\) and \(\Delta(q_i,s_j)\) with \(i \neq j\) so that only \(\Delta(s_i,s_j)\) and \(\Delta(q_i,s_i)\) belong to \(\mathcal{C}_{{\mathrm{\small OD}}}(\overline{H}_k)\). Hence, we obtained \(\mathcal{C}_{{\mathrm{\small OD}}}(\overline{H}_k) = {\cal{R}}_{|S|}^{|S|-1} \cup {\cal{R}}_{|Q|}^2\). Finally, this implies \(\gamma^{\rm{OD}}(\overline{H}_k) = 2 + (k-1) = k+1\) by the result from [31]. ◻

Proof. Consider a thin headless spider \(H_k=(Q \cup S, E)\) with \(k \geq 4\). \(\mathcal{H}_{{\mathrm{\small OD}}}(H_k)\) is composed of the closed neighborhoods

• \(N[s_i] = \{s_i,q_i\}\) for all \(s_i \in S\),

• \(N[q_i] = Q \cup \{s_i\}\) for all \(q_i \in Q\)

and the symmetric differences

• \(\Delta(s_i,s_j) = \{q_i,q_j\}\) for all distinct \(s_i,s_j \in S\),

• \(\Delta(q_i,q_j) = \{q_i,q_j\} \cup \{s_i,s_j\}\) for all distinct \(q_i,q_j \in Q\),

• \(\Delta(q_i,s_j) = \begin{cases} Q \cup \{s_i\}, &if i=j; \\ (Q \setminus \{q_i,q_j\}) \cup \{s_i\}, &if i \neq j.\\ \end{cases}\)

We deduce that in \(\mathcal{C}_{{\mathrm{\small OD}}}(H_k)\) with \(k \geq 4\) only

• \(N[s_i] = \{s_i,q_i\}\) for all \(s_i \in S\),

• \(\Delta(s_i,s_j) = \{q_i,q_j\}\) for all distinct \(s_i,s_j \in S\)

remain and thus \(\mathcal{C}_{{\mathrm{\small OD}}}(H_k) = H_k\) follows. Hence \(\mathcal{C}_{{\mathrm{\small OD}}}(H_k)\) contains the disjoint hyperedges \(\{q_i,s_i\}\) for \(1 \leq i \leq k\) which shows \(\gamma^{\rm{OD}}(H_k) \geq k\). On the other hand, \(Q\) is clearly a cover of \(\mathcal{C}_{{\mathrm{\small OD}}}(H_k) = H_k\) of cardinality \(k\), which finally implies \(\gamma^{\rm{OD}}(H_k) = k\). ◻

Proof. Consider an extended thin spider \(E_k=(Q \cup S, E)\) with \(k \geq 4\). In order to determine \(\mathcal{C}_{{\mathrm{\small X}}}(E_k)\) and \(\gamma^{\rm{X}}(E_k)\) for \({\mathrm{\small X}}\in \{{\mathrm{\small OD}},{\mathrm{\small OTD}}\}\), we first construct the X-hypergraphs. Recall that the following hyperedges are involved: the closed or open neighborhoods

• \(N[s_0] = \{s_0\} \cup (Q \setminus\{q_k\})\) and \(N(s_0) =Q \setminus\{q_k\}\),

• \(N[s_i] = \{s_i,q_i\}\) and \(N(s_i) =\{q_i\}\) for \(1 \leq i \leq k\),

• \(N[q_i] = Q \cup \{s_0,s_i\}\) and \(N(q_i) =(Q \setminus\{q_i\}) \cup \{s_0,s_i\}\) for \(1 \leq i < k\),

• \(N[q_k] = Q \cup \{s_k\}\) and \(N(q_k) =(Q \setminus\{q_k\}) \cup \{s_k\}\),

and the symmetric differences of open neighborhoods of distinct vertices

• \(\Delta(s_0,s_i) = Q \setminus\{q_i,q_k\}\) for \(1 \leq i < k\),

• \(\Delta(s_0,s_k) = Q\),

• \(\Delta(s_0,q_i) = \{q_i,q_k\} \cup \{s_0,s_i\}\) for \(1 \leq i < k\),

• \(\Delta(s_0,q_k) = \{s_k\}\),

• \(\Delta(s_i,s_j) = \{q_i,q_j\}\) for \(1 \leq i < j \leq k\),

• \(\Delta(s_i,q_i) = Q \cup \{s_0,s_i\}\) for \(1 \leq i < k\),

• \(\Delta(s_k,q_k) = Q \cup \{s_k\}\),

• \(\Delta(s_i,q_j) = (Q \setminus \{q_i,q_j\}) \cup \{s_0,s_j\}\) for \(1 \leq j < i \leq k\),

• \(\Delta(s_i,q_k) = (Q \setminus \{q_i,q_k\}) \cup \{s_k\}\) for \(1 \leq i < k\),

• \(\Delta(q_i,q_j) = \{q_i,q_j\} \cup \{s_i,s_j\}\) for \(1 \leq j < i \leq k\),

• \(\Delta(q_i,q_k) = \{q_i,q_k\} \cup \{s_0,s_i,s_k\}\) for \(1 \leq i < k\).

The OD-hypergraph involves the closed neighborhoods and all symmetric differences, including

• \(\Delta(s_0,q_k) = \{s_k\}\),

• \(N[s_i] = \{s_i,q_i\}\) for \(1 \leq i < k\), and

• \(\Delta(s_i,s_j) = \{q_i,q_j\}\) for \(1 \leq i < j \leq k\),

which implies that all other hyperedges are redundant and \(V^0_{{\mathrm{\small OD}}}(E_k)=\{s_0\}\). The subset \(\{s_k\}\) and \(\{s_i,q_i\}\) for \(1 \leq i < k\) of disjoint hyperedges shows \(\gamma^{\rm{OD}}(E_k) \geq k\). On the other hand, \(Q \setminus \{q_k\} \cup \{s_k\}\) is clearly a cover of \(\mathcal{C}_{{\mathrm{\small OD}}}(E_k)\) of cardinality \(k\), which finally implies \(\gamma^{\rm{OD}}(E_k) = k\).

The OTD-hypergraph involves the open neighborhoods and all symmetric differences, including

• \(N(s_i) =\{q_i\}\) for \(1 \leq i \leq k\),

• \(\Delta(s_0,q_k) = \{s_k\}\),

which implies that all other hyperedges are redundant and \(V^0_{{\mathrm{\small OTD}}}(E_k)=S \setminus \{s_k\}\). This clearly shows that \(Q \cup \{s_k\}\) is the only minimum cover of \(\mathcal{C}_{{\mathrm{\small OTD}}}(E_k)\) and we have \(\gamma^{\rm{OTD}}(E_k) = k+1\). ◻

Proof. \(\mathcal{H}_{{\mathrm{\small OD}}}(T_k)\) is composed of the closed neighborhoods

• \(N[s_i] = \{s_i,c_i\}\) for all \(s_i \in S\),

• \(N[c_i] = N_C[c_i] \cup \{s_i\}\) for all \(c_i \in C\)

and the symmetric differences

• \(\Delta(s_i,s_j) = \{c_i,c_j\}\) for all distinct \(s_i,s_j \in S\),

• \(\Delta(c_i,c_j) = (N_C(c_i) \Delta N_C(c_j)) \cup \{s_i,s_j\}\) for all distinct \(c_i,c_j \in C\),

• \(\Delta(c_i,s_j) = \begin{cases} N[c_i], &if i=j; \\ (N_C(c_i) \cup \{s_i\}) \Delta \{c_j\}, &if i \neq j.\\ \end{cases}\)

This shows that \(N[s_i]\) and \(\Delta(s_i,s_j)\) belong to \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\) which further implies that the following hyperedges from \(\mathcal{H}_{OD}(T_k)\) are redundant:

• \(N[c_i] = N_C[c_i] \cup \{s_i\}\) for all \(c_i \in C\),

• \(\Delta(c_i,c_j)\) if \(|N_C(c_i) \Delta N_C(c_j)| \geq 2\),

• \(\Delta(c_i,s_j)\) if \(c_i, c_j\) are non-adjacent or if \(c_i, c_j\) are adjacent but \(|N_C(c_i)| \geq 3\).

In the remaining cases, \(\Delta(c_i,c_j)\) and \(\Delta(c_i,s_j)\) belong to \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\). ◻

Proof. Consider a thin sun \(T_k=(C \cup S, E)\) with \(k \geq 4\) and without open \(C\)-twins. By Lemma 15, the OD-clutter \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\) contains \(\{s_i,c_i\}\) for all \(s_i \in S\), which implies the lower bound \(\gamma^{\rm{OD}}(T_k) \geq k\). On the other hand, it is easy to verify that, by Lemma 15, all hyperedges of the OD-clutter \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\) have a nonempty intersection with \(C\) (when \(T_k\) has no open \(C\)-twins) so that \(C\) is a cover of \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\) of cardinality \(k\). Hence, \(C\) is a minimum OD-code and the assertion \(\gamma^{{\mathrm{\small OD}}}(T_k)=|C|=k\) follows. ◻

Proof. Consider an almost complete thin sun \(T_{2\ell}\) with \(\ell \geq 3\) where \(c_i,c_{i+\ell}\) form open \(C\)-twins. By Lemma 15, the OD-clutter \(\mathcal{C}_{{\mathrm{\small OD}}}(T_{2\ell})\) is composed of

• \(N[s_i] = \{s_i,c_i\}\) for all \(s_i \in S\),

• \(\Delta(s_i,s_j) = \{c_i,c_j\}\) for all distinct \(s_i,s_j \in S\),

• \(\Delta(c_i,c_{i+\ell}) = \{s_i,s_{i+\ell}\}\) for all \(c_i \in C\).

Hence, every cover of \(\mathcal{C}_{{\mathrm{\small OD}}}(T_{2\ell})\) has to contain at least all but one vertex from \(C\) and one of \(\{s_i,s_{i+\ell}\}\) for all \(1 \leq i \leq \ell\), showing that \(\gamma^{\rm{OD}}(T_{2\ell}) \geq 3\ell - 1\). We next observe that \(V' = \{s_1, \ldots, s_{\ell}\} \cup C \setminus \{c_j\}\) for some \(j \in \{1, \ldots, {\ell}\}\) is a cover of \(\mathcal{C}_{{\mathrm{\small OD}}}(T_{2\ell})\). Indeed, \(V'\) meets all

• \(N[s_i] = \{s_i,c_i\}\) in \(s_i\) for \(1 \leq i \leq \ell\) and in \(c_i\) for \(\ell+1 \leq i \leq 2\ell\),

• \(\Delta(s_i,s_j) = \{c_i,c_j\}\) as \(V'\) contains all but one vertex from \(C\),

• \(\Delta(c_i,c_{i+\ell}) = \{s_i,s_{i+\ell}\}\) in \(s_i\) for \(1 \leq i \leq \ell\).

Hence, \(V'\) is an OD-code of \(T_{2\ell}\) and \(\gamma^{\rm{OD}}(T_{2\ell}) = 3\ell - 1\) follows. Furthermore, from [11] we deduce that the OTD-clutter \(\mathcal{C}_{{\mathrm{\small OTD}}}(T_{2\ell})\) is composed of

• \(N(s_i) = \{c_i\}\) for all \(s_i \in S\),

• \(\Delta(c_i,c_{i+\ell}) = \{s_i,s_{i+\ell}\}\) for all \(c_i \in C\).

For an almost complete thin sun \(T_{2\ell}\) with \(\ell \geq 3\), this implies that \(C \cup \{s_1, \ldots, s_{\ell}\}\) is a minimum OTD-code of \(T_{2\ell}\) and, hence, \(\gamma^{\rm{OTD}}(T_{2\ell}) = 3\ell\) follows. ◻

Proof. Let \(G=(V,E)\) be an OD-admissible graph. By the definition of \(\mathcal{F}^1_{{\mathrm{\small OD}}}(G)\), we clearly have \(x_v = 1\) for all forced vertices \(v \in \mathcal{F}^1_{{\mathrm{\small OD}}}(G)\). This makes the non-negativity constraints for forced vertices redundant so that only \(x_v \geq 0\) for all vertices \(v \not\in \mathcal{F}^1_{{\mathrm{\small OD}}}(G)\) remain.

From Theorem 9 by [32] it is further known that the only facet-defining (i.e. essential) inequalities of a covering polyhedron \(P(M)\) with integer coefficients and right hand side equal to \(1\) are those of the defining system \(M \mathbf{x} \geq \mathbf{1}\). Hence, for \(M = M_{{\mathrm{\small OD}}}(G)\), all constraints \(\sum_{v \in F}x_v \geq 1\) for all hyperedges \(F \in \mathcal{F}^2_{{\mathrm{\small OD}}}(G)\) are facet-defining for \(P_{{\mathrm{\small OD}}}(G)\). ◻

Proof. Let \(G=(V,E)\) be either a clique \(K_n\) with \(n \geq 2\) or a matching \(kK_2\) with \(k \geq 1\) and \(n=2k\). From Lemma 8 and the proof of Lemma 9, respectively, we see that \(\mathcal{C}_{{\mathrm{\small OD}}}(K_n)= {\cal{R}}_n^2=K_n\) and \(\mathcal{C}_{{\mathrm{\small OD}}}(kK_2)= {\cal{R}}_{2k}^2=K_{2k}\) holds. Hence, \(\mathcal{C}_{{\mathrm{\small OD}}}(G)\) is in both cases a complete \(2\)-rose of order \(n\) and \(P_{{\mathrm{\small OD}}}(G)\) is accordingly given by non-negativity constraints for all vertices \(v \in V\) and constraints \(x(V') \geq |V'|-1\) for all subsets \(V' \subseteq V\) with \(|V'| \geq 2\) by Theorem 11 from [27]. ◻

Proof. Consider a thick headless spider \(\overline{H}_k=(Q \cup S, E)\) with \(k \geq 4\). From Lemma 12, we have \(\mathcal{C}_{OD}(\overline{H}_k) = {\cal{R}}_{|S|}^{|S|-1} \cup {\cal{R}}_{|Q|}^2\). By \(\mathcal{F}^1_{{\mathrm{\small OD}}}(\overline{H}_k) = \emptyset\), we have non-negativity constraints for all vertices. Applying Theorem 11 from [27] on polyhedra associated to complete \(q\)-roses shows that \(P_{{\mathrm{\small OD}}}(\overline{H}_k)\) is given by non-negativity constraints for all vertices and the constraints

• \(x(V') = \sum_{v \in V'}x_v \geq |V'|-k+2\) for all \(V' \subseteq S\) with \(|V'| \geq k-1\),

• \(x(V') = \sum_{v \in V'}x_v \geq |V'|-1\) for all \(V' \subseteq Q\) with \(|V'| \geq 2\).

 ◻

Proof. Consider a thin headless spider \(H_k=(Q \cup S, E)\) with \(k \geq 4\). From Lemma 13, we have \(\mathcal{C}_{{\mathrm{\small OD}}}(H_k) = H_k\). Hence \(\mathcal{F}_{{\mathrm{\small OD}}}(H_k)\) is composed of the matching \(\{q_i,s_i\}\) for \(1 \leq i \leq k\) and the complete \(2\)-rose \({\cal{R}}_{|Q|}^2\).

By \(\mathcal{F}^1_{{\mathrm{\small OD}}}(H_k) = \emptyset\), we have non-negativity constraints for all vertices. Moreover, \(P_{{\mathrm{\small OD}}}(H_k)\) has clearly the constraints \(x(V') \geq |V'|-1\) for all \(V' \subseteq Q\) with \(|V'| \geq 2\) by Theorem 11 from [27] and Theorem 10 from [33]. Finally, \(x_{q_i} + x_{s_i} \geq 1\) define facets for \(1 \leq i \leq k\) by Theorem 9 from [32], and it is easy to see that no further constraints are needed to describe \(P_{{\mathrm{\small OD}}}(H_k)\) (as each \(x_{s_i}\) occurs in exactly one constraint different from a non-negativity constraint). ◻

Proof. Consider a sunlet \(T_k=(C \cup S, E)\) with \(k \geq 5\). By Lemma 15, the OD-clutter \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\) is composed of

• \(N[s_i] = \{s_i,c_i\}\) for all \(s_i \in S\),

• \(\Delta(c_i,s_{i-1}) = \{s_i,c_{i-1}\}\) and \(\Delta(c_i,s_{i+1}) = \{s_i,c_{i+1}\}\) for all \(c_i \in C\) (since we have \(\Delta(c_i,s_{i \pm 1}) = \{s_i,c_{i-1},\\ c_{i+1}\} \Delta \{c_{i \pm 1}\}\)),

• \(\Delta(s_i,s_j) = \{c_i,c_j\}\) for all distinct \(s_i,s_j \in S\).

Hence, in \(\mathcal{C}_{{\mathrm{\small OD}}}(T_k)\), \(C\) induces a \(K_k\), and all vertex subsets \(\{s_i,c_{i-1},c_i,c_{i+1}\}\) induce a \(K_4\) for \(1 \leq i \leq k\). Accordingly, \(\mathcal{F}^1_{{\mathrm{\small OD}}}(T_k) = \emptyset\) implies that \(P_{{\mathrm{\small OD}}}(T_k)\) has non-negativity constraints for all vertices. Moreover, we deduce from Theorem 11 by [27] and Theorem 10 from [33] that \(P_{{\mathrm{\small OD}}}(T_k)\) has the constraints

• \(x(V') = \sum_{v \in V'}x_v \geq |V'|-1\) for all \(V' \subseteq \{s_i,c_{i-1},c_i,c_{i-+}\}\) with \(|V'| \geq 2\) and \(1 \leq i \leq k\),

• \(x(C') = \sum_{v \in C'}x_v \geq |C'|-1\) for all \(C' \subseteq C\) with \(|C'| \geq 2\).

 ◻

Proof. Consider an almost complete thin sun \(T_{2\ell}\) with \(\ell \geq 3\) where \(c_i,c_{i+\ell}\) form open \(C\)-twins. Recall that, by Lemma 15, the OD-clutter \(\mathcal{C}_{{\mathrm{\small OD}}}(T_{2\ell})\) is composed of

• \(N[s_i] = \{s_i,c_i\}\) for all \(s_i \in S\),

• \(\Delta(s_i,s_j) = \{c_i,c_j\}\) for all distinct \(s_i,s_j \in S\),

• \(\Delta(c_i,c_{i+\ell}) = \{s_i,s_{i+\ell}\}\) for all \(c_i \in C\).

Hence, in \(\mathcal{C}_{{\mathrm{\small OD}}}(T_{2\ell})\), \(C\) induces a \(K_k\), and all vertex subsets \(\{s_i,c_i,c_{i+ \ell},s_{i+\ell}\}\) induce a \(C_4\) for \(1 \leq i \leq \ell\). Accordingly, \(\mathcal{F}^1_{{\mathrm{\small OD}}}(T_{2\ell}) = \emptyset\) implies that \(P_{{\mathrm{\small OD}}}(T_{2\ell})\) has non-negativity constraints for all vertices. Moreover, \(P_{{\mathrm{\small OD}}}(T_{2\ell})\) has the constraints

• \(x_{s_i} + x_{s_{i+\ell}} \geq 1\) for \(1 \leq i \leq \ell\),

• \(x_{s_i} + x_{c_i} \geq 1\) for \(1 \leq i \leq 2\ell\),

from the defining system and by Theorem 11 from [27] and Theorem 10 from [33] in addition the constraints

• \(x(C') = \sum_{v \in C'}x_v \geq |C'|-1\) for all \(C' \subseteq C\) with \(|C'| \geq 2\).

 ◻