# Open-Separating Dominating Codes in Graphs

Dipayan Chakraborty, Annegret Wagler

► To cite this version:

Dipayan Chakraborty, Annegret Wagler. Open-Separating Dominating Codes in Graphs. International Symposium on Combinatorial Optimization, May 2024, Tenerife (Canary Islands), Spain. pp.137-151, 10.1007/978-3-031-60924-4_11. hal-04615473

HAL Id: hal-04615473

https://hal.science/hal-04615473

Submitted on 18 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Open-Separating Dominating Codes in Graphs

Dipayan Chakraborty, Annegret Wagler

► To cite this version:

Dipayan Chakraborty, Annegret Wagler. Open-Separating Dominating Codes in Graphs. International Symposium on Combinatorial Optimization, May 2024, Tenerife (Canary Islands), Spain. pp.137-151, 10.1007/978-3-031-60924-4_11. hal-04615473

HAL Id: hal-04615473

https://hal.science/hal-04615473v1

Submitted on 18 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Open-separating dominating codes in graphs

Dipayan Chakraborty¹,²[0000-0001-7169-7288] and Annegret K. Wagler¹

¹ Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France
{dipayan.chakraborty,annegret.wagler}@uca.fr

² Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa

**Abstract.** Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set $C$ of a graph $G$ such that the neighbourhoods of all vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ is often referred to as a *code* in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called *open-separating dominating code*, or *OSD-code* for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OSD-codes. Due to the emergence of a close and yet difficult to establish relation of the OSD-codes with another well-studied code in the literature called open locating dominating codes, or OLD-codes for short, we compare the two on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OSD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OSD-codes, again in relation to OLD-codes of some graph families already studied in this context.

**Keywords:** open-separating codes · dominating sets · open locating-dominating codes · NP-completeness · hypergraphs · polyhedra

## 1 Introduction

The problem of placing surveillance devices in buildings to locate an intruder (like a fire, a thief or a saboteur) leads naturally to different location-domination type problems in the graph modeling the building (where rooms are represented as vertices and connections between rooms as edges). Depending on the characteristics of the detection devices (to detect an intruder only if it is present in the room where the detector is installed and/or to detect one in any neighbouring room), different kinds of dominating sets can be used to detect the existence of an intruder, whereas different locating-type properties are considered to exactly locate the position of an intruder in the building.
# Open-separating dominating codes in graphs

Dipayan Chakraborty$^{1,2[0000-0001-7169-7288]}$ and Annegret K. Wagler$^{1}$

¹ Université Clermont-Auvergne, CNRS, Mines de Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France
{dipayan.chakraborty,annegret.wagler}@uca.fr

² Department of Mathematics and Applied Mathematics, University of Johannesburg, Auckland Park, 2006, South Africa

**Abstract.** Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is to choose a suitable dominating set $C$ of a graph $G$ such that the neighbourhoods of all vertices of $G$ have distinct intersections with $C$. Such a dominating and separating set $C$ is often referred to as a *code* in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called *open-separating dominating code*, or *OSD-code* for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OSD-codes. Due to the emergence of a close and yet difficult to establish relation of the OSD-codes with another well-studied code in the literature called open locating dominating codes, or OLD-codes for short, we compare the two on various graph families. Finally, we also provide an equivalent reformulation of the problem of finding OSD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OSD-codes, again in relation to OLD-codes of some graph families already studied in this context.

**Keywords:** open-separating codes · dominating sets · open locating-dominating codes · NP-completeness · hypergraphs · polyhedra

## 1 Introduction

The problem of placing surveillance devices in buildings to locate an intruder (like a fire, a thief or a saboteur) leads naturally to different location-domination type problems in the graph modeling the building (where rooms are represented as vertices and connections between rooms as edges). Depending on the characteristics of the detection devices (to detect an intruder only if it is present in the room where the detector is installed and/or to detect one in any neighbouring room), different kinds of dominating sets can be used to detect the existence of an intruder, whereas different locating-type properties are considered to exactly locate the position of an intruder in the building.
More precisely, let $G = (V(G), E(G)) = (V, E)$ be a graph and let $N(v) = \{u \in V : uv \in E\}$ (respectively, $N[v] = N(v) \cup \{v\}$) denote the open neighbourhood (respectively, closed neighborhood) of a vertex $v \in V$. A subset $C \subseteq V$ is dominating (respectively, total-dominating) if $N[v] \cap C$ (respectively, $N(v) \cap C$) is a non-empty set for each $v \in V$. Moreover, $C \subseteq V$ is closed-separating (respectively, open-separating) if $N[v] \cap C$ (respectively, $N(v) \cap C$) is a unique set for each $v \in V$. Furthermore, the set $C$ is locating if $N(v) \cap C$ is a unique set for each $v \in V \setminus C$.

So far, the following combinations of location / separation and domination properties have been studied in the literature over the last decades:

- closed-separation with domination and total-domination leading to *identifying codes* (ID-codes for short) [11] and *differentiating total-dominating codes* (DTD-codes for short) [12], respectively;

- location with domination and total-domination leading to *locating-dominating codes* (LD-codes for short) [16] and *locating total-dominating codes* (LTD-codes for short) [12], respectively;

- open-separation with total-domination leading to *open locating-dominating codes* (OLD-codes for short) [17].

Such problems have several applications, e.g. in fault-detection in multiprocessor networks [11], locating threats/intruders in facilities using sensor networks [18], logical definability of graphs [15] and canonical labeling of graphs for the graph isomorphism problem [4], to name a few. An extensive internet bibliography containing over 500 articles around these topics is maintained by Jean and Lobstein [13].

In this paper, we aim at studying open-separation combined with domination. We call a subset $C \subseteq V$ of a graph $G = (V, E)$ an *open-separating dominating code* (OSD-code for short) if

- $N[v] \cap C$ is a non-empty set for each $v \in V$; and

- $N(v) \cap C$ is a unique set for each $v \in V$.

Note that not all graphs admit codes of all the studied types. Accordingly, in Section 2 of this paper, we address the conditions for the existence of the OSD-codes and their relations to codes of other types. It turns out that the OSD-codes possess a particularly close relationship with the OLD-codes as the minimum cardinalities of the two differ by at most one. Moreover, for any $X \in \{\text{ID, DTD, LD, LTD, OLD}\}$, the problem of determining an X-code of minimum cardinality $\gamma^X(G)$ of a graph $G$, called the *X-number* of $G$, has been shown to be NP-hard [7, 8, 17]. In Section 2, we show that NP-hardness holds for OSD-codes as well. Furthermore, in view of the close relationship between the OSD- and the OLD-numbers of a graph, we show that deciding whether the two numbers differ is NP-complete. This motivates us to compare the OSD- and the OLD-codes of graphs of different families in Section 3 and to study their related polyhedra in Section 4. We close with some concluding remarks and lines of future research.
More precisely, let $G = (V(G), E(G)) = (V, E)$ be a graph and let $N(v) = \{u \in V : uv \in E\}$ (respectively, $N[v] = N(v) \cup \{v\}$) denote the open neighbourhood (respectively, closed neighborhood) of a vertex $v \in V$. A subset $C \subseteq V$ is dominating (respectively, total-dominating) if $N[v] \cap C$ (respectively, $N(v) \cap C$) is a non-empty set for each $v \in V$. Moreover, $C \subseteq V$ is closed-separating (respectively, open-separating) if $N[v] \cap C$ (respectively, $N(v) \cap C$) is a unique set for each $v \in V$. Furthermore, the set $C$ is locating if $N(v) \cap C$ is a unique set for each $v \in V \setminus C$.

So far, the following combinations of location / separation and domination properties have been studied in the literature over the last decades:

- closed-separation with domination and total-domination leading to *identifying codes* (ID-codes for short) [11] and *differentiating total-dominating codes* (DTD-codes for short) [12], respectively;

- location with domination and total-domination leading to *locating-dominated codes* (LD-codes for short) [16] and *locating total-dominating codes* (LTD-codes for short) [12], respectively;

- open-separation with total-domination leading to *open locating-dominated codes* (OLD-codes for short) [17].

Such problems have several applications, e.g. in fault-detection in multiprocessor networks [11], locating threats/intruders in facilities using sensor networks [18], logical definability of graphs [15] and canonical labeling of graphs for the graph isomorphism problem [4], to name a few. An extensive internet bibliography containing over 500 articles around these topics is maintained by Jean and Lobstein [13].

In this paper, we aim at studying open-separation combined with domination. We call a subset $C \subseteq V$ of a graph $G = (V, E)$ an *open-separating dominating code* (OSD-code for short) if

- $N[v] \cap C$ is a non-empty set for each $v \in V$; and

- $N(v) \cap C$ is a unique set for each $v \in V$.

Note that not all graphs admit codes of all the studied types. Accordingly, in Section 2 of this paper, we address the conditions for the existence of the OSD-codes and their relations to codes of other types. It turns out that the OSD-codes possess a particularly close relationship with the OLD-codes as the minimum cardinalities of the two differ by at most one. Moreover, for any $X \in \{\text{ID, DTD, LD, LTD, OLD}\}$, the problem of determining an X-code of minimum cardinality $\gamma^X(G)$ of a graph $G$, called the *X-number* of $G$, has been shown to be NP-hard [7, 8, 17]. In Section 2, we show that NP-hardness holds for OSD-codes as well. Furthermore, in view of the close relationship between the OSD- and the OLD-numbers of a graph, we show that deciding whether the two numbers differ is NP-complete. This motivates us to compare the OSD- and the OLD-codes of graphs of different families in Section 3 and to study their related polyhedra in Section 4. We close with some concluding remarks and lines of future research.
## 2 Existence, bounds and hardness

We next address fundamental questions concerning the existence of OSD-codes, bounds for OSD-numbers and the hardness of the OSD-problem.

*Existence of OSD-codes.* It has been observed in the literature that the studied domination and separation properties may not apply to all graphs, see for example [11, 12, 17]. More precisely,

- total-domination excludes the occurrence of *isolated vertices* in graphs, that is, vertices $v$ with $N(v) = \emptyset$;

- closed-separation (respectively, open-separation) excludes the occurrence of *closed twins* (respectively, *open twins*), that is, distinct vertices $u, v$ with $N[u] = N[v]$ (respectively, $N(u) = N(v)$).

Calling a graph $G$ to be *X-admissible* if $G$ has an X-code, we see that while, for example, every graph $G$ is LD-admissible, a graph $G$ is OLD-admissible if and only if $G$ has neither isolated vertices nor open twins. Accordingly, we conclude the following regarding the existence of OSD-codes of graphs.

**Corollary 1.** *A graph $G$ is OSD-admissible if and only if $G$ has no open twins.*

Since any two distinct isolated vertices of a graph are open twins with the empty set as both their open neighbourhoods, Corollary 1 further implies that an OSD-admissible graph has at most one isolated vertex.

*Bounds on OSD-numbers and their relations to other X-numbers.* We prove the following general bounds on the OSD-number of a graph in terms of the number of vertices of the graph. The upper bound is based on results in [6].

**Theorem 1.** *For a graph $G$ on $n \ge 2$ vertices without open twins and any isolated vertices, we have $\log n \le \gamma^{\text{OSD}}(G) \le n - 1$.*

The following are bounds on the OSD-numbers in relation to other X-numbers.

**Theorem 2.** Let $G = (V, E)$ be an OSD-admissible graph.

(a) We have $\gamma^{\text{LD}}(G) \le \gamma^{\text{OSD}}(G)$.

(b) If $G$ is a disjoint union of a graph $G'$ and an isolated vertex, then we have $\gamma^{\text{OSD}}(G) = \gamma^{\text{OLD}}(G') + 1$; otherwise, $\gamma^{\text{OLD}}(G) - 1 \le \gamma^{\text{OSD}}(G) \le \gamma^{\text{OLD}}(G)$.

*Proof (sketch).* (a) It can be verified that any minimum OSD-code $C$ of $G$ is also a locating set of $G$, and hence, the result holds.

(b) Let $G$ be a disjoint union of a graph $G'$ and an isolated vertex $v$. Moreover, let $C$ be any minimum OSD-code of $G$. Then, we must have $N(v) \cap C = \emptyset$. Hence, the result follows from the fact that the set $C - \{v\}$ must total-dominate all vertices in $V - \{v\}$, that is, $C - \{v\}$ is an OLD-code of $G'$.

Let us now assume that $G$ has no isolated vertices. Then, $G$ is also OLD-admissible. The inequality $\gamma^{\text{OSD}}(G) \le \gamma^{\text{OLD}}(G)$ follows from the fact that any OLD-code of $G$ is also an OSD-code of $G$. To prove the other inequality, consider
## 2 Existence, bounds and hardness

We next address fundamental questions concerning the existence of OSD-codes, bounds for OSD-numbers and the hardness of the OSD-problem.

*Existence of OSD-codes.* It has been observed in the literature that the studied domination and separation properties may not apply to all graphs, see for example [11, 12, 17]. More precisely,

- total-domination excludes the occurrence of *isolated vertices* in graphs, that is, vertices $v$ with $N(v) = \emptyset$;

- closed-separation (respectively, open-separation) excludes the occurrence of *closed twins* (respectively, *open twins*), that is, distinct vertices $u, v$ with $N[u] = N[v]$ (respectively, $N(u) = N(v)$).

Calling a graph $G$ to be *X-admissible* if $G$ has an X-code, we see that while, for example, every graph $G$ is LD-admissible, a graph $G$ is OLD-admissible if and only if $G$ has neither isolated vertices nor open twins. Accordingly, we conclude the following regarding the existence of OSD-codes of graphs.

**Corollary 1.** *A graph $G$ is OSD-admissible if and only if $G$ has no open twins.*

Since any two distinct isolated vertices of a graph are open twins with the empty set as both their open neighbourhoods, Corollary 1 further implies that an OSD-admissible graph has at most one isolated vertex.

*Bounds on OSD-numbers and their relations to other X-numbers.* We prove the following general bounds on the OSD-number of a graph in terms of the number of vertices of the graph. The upper bound is based on results in [6].

**Theorem 1.** For a graph $G$ on $n \ge 2$ vertices without open twins and any isolated vertices, we have $\log n \le \gamma^{\text{OSD}}(G) \le n - 1$.

The following are bounds on the OSD-numbers in relation to other X-numbers.

**Theorem 2.** Let $G = (V, E)$ be an OSD-admissible graph.

(a) We have $\gamma^{\text{LD}}(G) \le \gamma^{\text{OSD}}(G)$.

(b) If $G$ is a disjoint union of a graph $G'$ and an isolated vertex, then we have $\gamma^{\text{OSD}}(G) = \gamma^{\text{OLD}}(G') + 1$; otherwise, $\gamma^{\text{OLD}}(G) - 1 \le \gamma^{\text{OSD}}(G) \le \gamma^{\text{OLD}}(G)$.

*Proof (sketch).* (a) It can be verified that any minimum OSD-code $C$ of $G$ is also a locating set of $G$, and hence, the result holds.

(b) Let $G$ be a disjoint union of a graph $G'$ and an isolated vertex $v$. Moreover, let $C$ be any minimum OSD-code of $G$. Then, we must have $N(v) \cap C = \emptyset$. Hence, the result follows from the fact that the set $C - \{v\}$ must total-dominate all vertices in $V - \{v\}$, that is, $C - \{v\}$ is an OLD-code of $G'$.

Let us now assume that $G$ has no isolated vertices. Then, $G$ is also OLD-admissible. The inequality $\gamma^{\text{OSD}}(G) \le \gamma^{\text{OLD}}(G)$ follows from the fact that any OLD-code of $G$ is also an OSD-code of $G$. To prove the other inequality, consider
<table><caption>Table 1: Comparison of OSD-numbers and other X-numbers of some graphs, where $X \in \{\text{ID, DTD, LTD}\}$. The black vertices constitute the respective codes.</caption><thead><tr><th>X</th><th>X-code</th><th>OSD-code</th><th>Graph name</th><th>γ<sup>OSD</sup>(G)</th><th>γ<sup>X</sup>(G)</th></tr></thead><tbody><tr><td rowspan="2">X=ID</td><td></td><td></td><td>Gem</td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>⟨ Gem ⟩</td><td>5</td><td>4</td></tr><tr><td rowspan="2">X=DTD</td><td></td><td></td><td>Bull</td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>Bow</td><td>5</td><td>3</td></tr><tr><td rowspan="2">X=LTD</td><td></td><td></td><td>2P<sub>2</sub></td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>P<sub>4</sub></td><td>3</td><td>2</td></tr></tbody></table>

### OSD

*Instance.* $(G, \ell)$: An OSD-admissible graph $G$ and a non-negative integer $\ell$.

*Question.* Is $\gamma^{\text{OSD}}(G) \le \ell$?

**Theorem 3.** OSD is NP-complete.

As exhibited in Theorem 2(b), given an OLD-admissible graph $G$, we have either $\gamma^{\text{OLD}}(G) = \gamma^{\text{OSD}}(G)$ or $\gamma^{\text{OLD}}(G) = \gamma^{\text{OSD}}(G) + 1$. This poses the question how hard it is, for a given graph, to decide which of the two relations hold.

a minimum OSD-code $C$ of $G$. If $C$ is also an OLD-code of $G$, then the result holds trivially. Otherwise, $C$ is not a total-dominating set of $G$ which implies that there exists a vertex $v$ of $G$ such that $C \cap N(v) = \emptyset$. One can show that $v$ is the only vertex with this property. Thus, $C \cup \{u\}$ for some neighbour $u$ of $v$ (which exists as $v$ is not an isolated vertex of $G$) is a total-dominating set of $G$ and hence, is also an OLD-code of $G$. Therefore, we have $\gamma^{\text{OLD}}(G) \le |C|+1 = \gamma^{\text{OSD}}(G)+1$. □

The tightness and extremal examples of graphs whose OSD-numbers attain the above bounds are discussed in the next section. Apart from the relations in Theorem 2, the OSD-numbers of graphs are not generally comparable to the other X-numbers with $X \in \{\text{ID, DTD, LTD}\}$, see Table 1 for an illustration.

*Hardness of the OSD-problem.* It has been established in the literature that all the previously studied X-problems are NP-hard [7, 8, 17]. We next address the hardness of the OSD-problem.
<table><caption>Table 1: Comparison of OSD-numbers and other X-numbers of some graphs, where $X \in \{\text{ID, DTD, LTD}\}$. The black vertices constitute the respective codes.</caption><thead><tr><th>X</th><th>X-code</th><th>OSD-code</th><th>Graph name</th><th>γ<sup>OSD</sup>(G)</th><th>γ<sup>X</sup>(G)</th></tr></thead><tbody><tr><td rowspan="2">X=ID</td><td></td><td></td><td>Gem</td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>⟨ Gem ⟩</td><td>5</td><td>4</td></tr><tr><td rowspan="2">X=DTD</td><td></td><td></td><td>Bull</td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>Bow</td><td>5</td><td>3</td></tr><tr><td rowspan="2">X=LTD</td><td></td><td></td><td>2P<sub>2</sub></td><td>3</td><td>4</td></tr><tr><td></td><td></td><td>P<sub>4</sub></td><td>3</td><td>2</td></tr></tbody></table>

### OSD

*Instance.* $(G, \ell)$: An OSD-admissible graph $G$ and a non-negative integer $\ell$.

*Question.* Is $\gamma^{\text{OSD}}(G) \le \ell$?

**Theorem 3.** OSD is NP-complete.

As exhibited in Theorem 2(b), given an OLD-admissible graph $G$, we have either $\gamma^{\text{OLD}}(G) = \gamma^{\text{OSD}}(G)$ or $\gamma^{\text{OLD}}(G) = \gamma^{\text{OSD}}(G) + 1$. This poses the question how hard it is, for a given graph, to decide which of the two relations hold.

a minimum OSD-code $C$ of $G$. If $C$ is also an OLD-code of $G$, then the result holds trivially. Otherwise, $C$ is not a total-dominating set of $G$ which implies that there exists a vertex $v$ of $G$ such that $C \cap N(v) = \emptyset$. One can show that $v$ is the only vertex with this property. Thus, $C \cup \{u\}$ for some neighbour $u$ of $v$ (which exists as $v$ is not an isolated vertex of $G$) is a total-dominating set of $G$ and hence, is also an OLD-code of $G$. Therefore, we have $\gamma^{\text{OLD}}(G) \le |C|+1 = \gamma^{\text{OSD}}(G)+1$. □

The tightness and extremal examples of graphs whose OSD-numbers attain the above bounds are discussed in the next section. Apart from the relations in Theorem 2, the OSD-numbers of graphs are not generally comparable to the other X-numbers with $X \in \{\text{ID, DTD, LTD}\}$, see Table 1 for an illustration.

*Hardness of the OSD-problem.* It has been established in the literature that all the previously studied X-problems are NP-hard [7, 8, 17]. We next address the hardness of the OSD-problem.
OLD= OSD+1

*Instance.* (*G*, *ℓ*): An OLD-admissible graph *G* and a non-negative integer *ℓ*.

*Question.* Is $\gamma^{\text{OSD}}(G) = \ell$ and $\gamma^{\text{OLD}}(G) = \ell + 1$?

As the next theorem shows, despite the closeness, it is hard to decide if the OSD-
and the OLD-numbers on a graph differ.

**Theorem 4.** OLD= OSD+1 is NP-complete.

To prove Theorems 3 and 4, we reduce in polynomial-time another well known
NP-complete problem of Linear Satisfiability (LSAT) to the above two problems.
The problem of LSAT is stated formally as the following.

LSAT

*Instance.* *I* = (*X*, *Y*): A set *X* of variables and a set *Y* of clauses over *X* such that

1. each clause contains exactly 3 variables of the form *x* or *x̄* (each referred to as a *literal*), for some *x* ∈ *X*; and

2. each literal is contained in at most two clauses.

3. any two distinct clauses have at most one variable in common.

*Question.* Is there a satisfactory truth assignment for the instance?

The proofs of Theorems 3 and 4 are based on the following construction of a
suitable LSAT instance and several technical lemmatas.

**Construction 1** Let $I = (X, Y)$ be an instance of LSAT such that $|X| = k$ and $|Y| = l$. For each variable $x \in X$, construct a (variable gadget) graph $G_x$ on 5 vertices, namely, $v^x, v^{\bar{x}}, a_1^x, a_2^x, a_3^x$, as shown in Figure 1a. Next, for each clause $y \in Y$, take a (clause gadget) 3-path $P_y$ on vertices $u_1^y, u_2^y, u_3^y$ as in Figure 1b. Finally construct the graph $G_I$ on $5k + 3l$ vertices by adding edges between all pairs $(u_1^y, v^x)$ (respectively, $(u_1^y, v^{\bar{x}})$) of vertices if and only if $x$ (respectively, $\bar{x}$) is a literal in $y$. See Figure 1c.

3 OSD-numbers of some graph families

In this section, we study the OSD-numbers of graphs belonging to some well-
known graph families. Moreover, motivated by the hardness of deciding for which
graphs the OSD- and the OLD-numbers differ, we compare in the following
the two numbers on some chosen graph families. This comparison also exhibits
extremal cases for the upper bounds in Theorem 1.

*Cliques and their disjoint unions.* Cliques $K_n$ are clearly open twin-free so that for $n \ge 2$ both OSD- and OLD-codes exist. It is known that the following holds.

$$
\gamma^{\text{OLD}}(K_n) = \begin{cases} 2, & \text{if } n = 2; \\ n-1, & \text{if } n \ge 3. \end{cases}
$$
OLD= OSD+1

*Instance.* (*G*, *ℓ*): An OLD-admissible graph *G* and a non-negative integer *ℓ*.

*Question.* Is $\gamma^{\text{OSD}}(G) = \ell$ and $\gamma^{\text{OLD}}(G) = \ell + 1$?

As the next theorem shows, despite the closeness, it is hard to decide if the OSD-
and the OLD-numbers on a graph differ.

**Theorem 4.** OLD= OSD+1 is NP-complete.

To prove Theorems 3 and 4, we reduce in polynomial-time another well known
NP-complete problem of Linear Satisfiability (LSAT) to the above two problems.
The problem of LSAT is stated formally as the following.

LSAT

*Instance.* $I = (X, Y)$: A set $X$ of variables and a set $Y$ of clauses over $X$ such that

1. each clause contains exactly 3 variables of the form $x$ or $\bar{x}$ (each referred to as a *literal*), for some $x \in X$; and

2. each literal is contained in at most two clauses.

3. any two distinct clauses have at most one variable in common.

*Question.* Is there a satisfactory truth assignment for the instance?

The proofs of Theorems 3 and 4 are based on the following construction of a
suitable LSAT instance and several technical lemmatas.

**Construction 1** Let $I = (X, Y)$ be an instance of LSAT such that $|X| = k$ and $|Y| = l$. For each variable $x \in X$, construct a (variable gadget) graph $G_x$ on 5 vertices, namely, $v^x, v^{\bar{x}}, a_1^x, a_2^x, a_3^x$, as shown in Figure 1a. Next, for each clause $y \in Y$, take a (clause gadget) 3-path $P_y$ on vertices $u_1^y, u_2^y, u_3^y$ as in Figure 1b. Finally construct the graph $G_I$ on $5k + 3l$ vertices by adding edges between all pairs $(u_1^y, v^x)$ (respectively, $(u_1^y, v^{\bar{x}})$) of vertices if and only if $x$ (respectively, $\bar{x}$) is a literal in $y$. See Figure 1c.

3 OSD-numbers of some graph families

In this section, we study the OSD-numbers of graphs belonging to some well-
known graph families. Moreover, motivated by the hardness of deciding for which
graphs the OSD- and the OLD-numbers differ, we compare in the following
the two numbers on some chosen graph families. This comparison also exhibits
extremal cases for the upper bounds in Theorem 1.

*Cliques and their disjoint unions.* Cliques $K_n$ are clearly open twin-free so that for $n \ge 2$ both OSD- and OLD-codes exist. It is known that the following holds.

$$
\gamma^{\text{OLD}}(K_n) = \begin{cases} 2, & \text{if } n = 2; \\ n-1, & \text{if } n \ge 3. \end{cases}
$$
<figure><img src="image_2.png" /><figcaption>Fig. 1: Polynomial-time construction of the graph $G_I$ from an LSAT instance $I = (X, Y)$.</figcaption></figure>

**Lemma 1.** For a clique $K_n$ with $n \ge 2$, we have $\gamma^{\text{OSD}}(K_n) = n - 1$.

Hence, the OSD- and the OLD-numbers of cliques $K_n$ differ only for $n = 2$ and are equal for all $n \ge 3$. Moreover, the upper bound in Theorem 1 is attained for all $n \ge 3$. Consider now a graph $G = K_{n_1} + \dots + K_{n_k}$ that is the disjoint union of $k \ge 2$ cliques with $1 < n_1 \le \dots \le n_k$. It is well-known that the OLD-number of the disjoint union of two or more graphs is the sum of their OLD-numbers. Hence, we have

$$ \gamma^{\text{OLD}}(K_{n_1} + \dots + K_{n_k}) = \sum_{n_i=2} 2 + \sum_{n_i \ge 3} (n_i - 1). $$

To compare this with the corresponding OSD-numbers, we have the following.

**Lemma 2.** Let $G = K_{n_1} + \dots + K_{n_k}$ be a disjoint union of $k \ge 2$ cliques with $1 < n_1 \le \dots \le n_k$.

(a) If $n_1 = 2$, then $\gamma^{\text{OSD}}(G) = -1 + \sum_{n_i=2} 2 + \sum_{n_i \ge 3} (n_i - 1)$,

(b) If $n_1 \ge 3$, then $\gamma^{\text{OSD}}(G) = \sum_{1 \le i \le k} (n_i - 1)$.

Hence, for graphs $G$ that are disjoint unions of cliques, the OSD- and the OLD-numbers are equal if all components are cliques of order $\ge 3$, but differ otherwise. In particular, if $G$ is a matching (i.e. if $n_i = 2$ for all $1 \le i \le k$) and $k \ge 2$, the OLD-number of $G$ is strictly greater than its OSD-number, and the upper bound of $\gamma^{\text{OSD}}(G) = |V(G)| - 1$ from Theorem 1 is attained.
<figure><img src="image_2.png" /><figcaption>Fig. 1: Polynomial-time construction of the graph $G_I$ from an LSAT instance $I = (X, Y)$.</figcaption></figure>

**Lemma 1.** For a clique $K_n$ with $n \ge 2$, we have $\gamma^{\text{OSD}}(K_n) = n - 1$.

Hence, the OSD- and the OLD-numbers of cliques $K_n$ differ only for $n = 2$ and are equal for all $n \ge 3$. Moreover, the upper bound in Theorem 1 is attained for all $n \ge 3$. Consider now a graph $G = K_{n_1} + \dots + K_{n_k}$ that is the disjoint union of $k \ge 2$ cliques with $1 < n_1 \le \dots \le n_k$. It is well-known that the OLD-number of the disjoint union of two or more graphs is the sum of their OLD-numbers. Hence, we have

$$ \gamma^{\text{OLD}}(K_{n_1} + \dots + K_{n_k}) = \sum_{n_i=2} 2 + \sum_{n_i \ge 3} (n_i - 1). $$

To compare this with the corresponding OSD-numbers, we have the following.

**Lemma 2.** Let $G = K_{n_1} + \dots + K_{n_k}$ be a disjoint union of $k \ge 2$ cliques with $1 < n_1 \le \dots \le n_k$.

(a) If $n_1 = 2$, then $\gamma^{\text{OSD}}(G) = -1 + \sum_{n_i=2} 2 + \sum_{n_i \ge 3} (n_i - 1)$,

(b) If $n_1 \ge 3$, then $\gamma^{\text{OSD}}(G) = \sum_{1 \le i \le k} (n_i - 1)$.

Hence, for graphs $G$ that are disjoint unions of cliques, the OSD- and the OLD-numbers are equal if all components are cliques of order $\ge 3$, but differ otherwise. In particular, if $G$ is a matching (i.e. if $n_i = 2$ for all $1 \le i \le k$) and $k \ge 2$, the OLD-number of $G$ is strictly greater than its OSD-number, and the upper bound of $\gamma^{\text{OSD}}(G) = |V(G)| - 1$ from Theorem 1 is attained.
**Bipartite graphs.** A graph $G = (U \cup W, E)$ is bipartite if its vertex set can be partitioned into two stable sets $U$ and $W$ so that every edge of $G$ has one endpoint in $U$ and the other in $W$. We next exhibit families of bipartite graphs where the OSD- and the OLD-numbers differ.

For any integer $k \ge 1$, the half-graph $B_k = (U \cup W, E)$ is the bipartite graph with its stable vertex sets $U = \{u_1, \dots, u_k\}$ and $W = \{w_1, \dots, w_k\}$ and edges $u_i w_j$ if and only if $i \le j$ (see Figure 2a). In particular, we have $B_1 = K_2$, $B_2 = P_4$. Moreover, we clearly see that half-graphs are connected and open-twin-free and hence, are both OSD- and OLD-admissible.

In [10] it was shown that the only graphs whose OLD-numbers equal the order of the graph are the disjoint unions of half-graphs. In particular, we have $\gamma^{\text{OLD}}(B_k) = |V(B_k)| = 2k$. Now, let $G = (V, E)$ be a graph that is a disjoint union of half-graphs. By Theorem 2(b), therefore, we have $\gamma^{\text{OSD}}(G) \ge \gamma^{\text{OLD}}(G) - 1 = |V| - 1$. Moreover, by Theorem 1, we have $\gamma^{\text{OSD}}(G) \le |V| - 1$. Hence, combining the two inequalities, we get the following corollary.

**Corollary 2.** For a graph $G = (V, E)$ being the disjoint union of half-graphs, we have $\gamma^{\text{OSD}}(G) = |V| - 1$. In particular, for a half-graph $B_k$, we have $\gamma^{\text{OSD}}(B_k) = 2k - 1$.

Corollary 2 shows in particular that half-graphs and their disjoint unions are extremal examples of graphs whose OSD-numbers also attain the general upper bound in Theorem 1. We further note that the upper bound from Theorem 1 does not apply to OSD-admissible graphs having an isolated vertex. To see this, consider the graph $G = B_k + K_1$ for some $k \ge 1$. By Theorem 2(b), we have $\gamma^{\text{OSD}}(G) = \gamma^{\text{OLD}}(B_k) + 1 = 2k + 1 = |V(G)|$. As half-graphs and their disjoint unions are the only graphs whose OLD-numbers equal the order of the graph by [10], adding an isolated vertex to them yields the only graphs whose OSD-numbers equal the order of the graph.

A $k$-double star $D_k = (U \cup W, E)$ is the bipartite graph with its stable vertex sets $U = \{u_0, u_1, \dots, u_k\}$ and $W = \{w_1, \dots, w_k\}$ and edges $u_i w_i$ and $u_0 w_i$ for all $w_i \in W$ (see Figure 2b). Then, we have $D_1 = P_3$ and $D_2 = P_5$. Moreover, we clearly see that $k$-double stars with $k \ge 2$ are connected and open-twin-free and hence, are both OSD- and OLD-admissible. As the next Lemma shows, $k$-double stars also provide examples of bipartite graphs where the OLD- and the OSD-numbers disagree.

<figure><img src="image_3.png" /><figcaption>Fig. 2: The black vertices depict an OSD-code of the respective graph.</figcaption></figure>
**Bipartite graphs.** A graph $G = (U \cup W, E)$ is bipartite if its vertex set can be partitioned into two stable sets $U$ and $W$ so that every edge of $G$ has one endpoint in $U$ and the other in $W$. We next exhibit families of bipartite graphs where the OSD- and the OLD-numbers differ.

For any integer $k \ge 1$, the half-graph $B_k = (U \cup W, E)$ is the bipartite graph with its stable vertex sets $U = \{u_1, \dots, u_k\}$ and $W = \{w_1, \dots, w_k\}$ and edges $u_i w_j$ if and only if $i \le j$ (see Figure 2a). In particular, we have $B_1 = K_2$, $B_2 = P_4$. Moreover, we clearly see that half-graphs are connected and open-twin-free and hence, are both OSD- and OLD-admissible.

In [10] it was shown that the only graphs whose OLD-numbers equal the order of the graph are the disjoint unions of half-graphs. In particular, we have $\gamma^{\text{OLD}}(B_k) = |V(B_k)| = 2k$. Now, let $G = (V, E)$ be a graph that is a disjoint union of half-graphs. By Theorem 2(b), therefore, we have $\gamma^{\text{OSD}}(G) \ge \gamma^{\text{OLD}}(G) - 1 = |V| - 1$. Moreover, by Theorem 1, we have $\gamma^{\text{OSD}}(G) \le |V| - 1$. Hence, combining the two inequalities, we get the following corollary.

**Corollary 2.** For a graph $G = (V, E)$ being the disjoint union of half-graphs, we have $\gamma^{\text{OSD}}(G) = |V| - 1$. In particular, for a half-graph $B_k$, we have $\gamma^{\text{OSD}}(B_k) = 2k - 1$.

Corollary 2 shows in particular that half-graphs and their disjoint unions are extremal examples of graphs whose OSD-numbers also attain the general upper bound in Theorem 1. We further note that the upper bound from Theorem 1 does not apply to OSD-admissible graphs having an isolated vertex. To see this, consider the graph $G = B_k + K_1$ for some $k \ge 1$. By Theorem 2(b), we have $\gamma^{\text{OSD}}(G) = \gamma^{\text{OLD}}(B_k) + 1 = 2k + 1 = |V(G)|$. As half-graphs and their disjoint unions are the only graphs whose OLD-numbers equal the order of the graph by [10], adding an isolated vertex to them yields the only graphs whose OSD-numbers equal the order of the graph.

A $k$-double star $D_k = (U \cup W, E)$ is the bipartite graph with its stable vertex sets $U = \{u_0, u_1, \dots, u_k\}$ and $W = \{w_1, \dots, w_k\}$ and edges $u_i w_i$ and $u_0 w_i$ for all $w_i \in W$ (see Figure 2b). Then, we have $D_1 = P_3$ and $D_2 = P_5$. Moreover, we clearly see that $k$-double stars with $k \ge 2$ are connected and open-twin-free and hence, are both OSD- and OLD-admissible. As the next Lemma shows, $k$-double stars also provide examples of bipartite graphs where the OLD- and the OSD-numbers disagree.

<figure><img src="image_3.png" /><figcaption>Fig. 2: The black vertices depict an OSD-code of the respective graph.</figcaption></figure>
**Lemma 3.** For a $k$-double star $D_k$ with $k \ge 2$, we have $\gamma^{\text{OSD}}(D_k) = 2k-1$ and $\gamma^{\text{OLD}}(D_k) = 2k$.

*Split graphs.* A graph $G = (Q \cup S, E)$ is a *split graph* if its vertex set can be partitioned into a clique $Q$ and a stable set $S$. In order to study OSD-codes of split graphs and compare them with the OLD-codes, we restrict ourselves to split graphs $G$ without open twins and isolated vertices. This further implies that $G$ is connected and $Q$ non-empty (as, otherwise, every component not containing the clique $Q$ needs to be an isolated vertex from $S$, contradicting our assumptions). Figure 3 shows some small OLD-admissible graphs. It is easy to see that $\gamma^{\text{OSD}}(G)$ and $\gamma^{\text{OLD}}(G)$ differ for $G \in \{P_4, \text{gem}\}$ and are equal for $G \in \{\text{net, sun}\}$.

We next examine OSD-codes in two families of split graphs for which the exact OLD-numbers are known from [3]. A *headless spider* is a split graph with $Q = \{q_1, \dots, q_k\}$ and $S = \{s_1, \dots, s_k\}$. In addition, a headless spider is *thin* (respectively, *thick*) if $s_i$ is adjacent to $q_j$ if and only if $i = j$ (respectively, $i \neq j$). By definition, it is clear that the complement of a thin headless spider $H_k$ is a thick headless spider $\overline{H}_k$, and vice-versa. We have $H_2 = \overline{H}_2 = P_4$, the two headless spiders $H_3 = \text{net}$ and $\overline{H}_3 = \text{sun}$ are depicted in Figures 3(c) and 3(d), respectively. Moreover, it is easy to check that the thin and the thick headless spiders have no twins.

In [3], it was shown that $\gamma^{\text{OLD}}(H_k) = k$ for $k \ge 3$ and $\gamma^{\text{OLD}}(\overline{H}_k) = k+1$ for $k \ge 3$. We next analyse the OSD-numbers of the thin and the thick headless spiders.

**Lemma 4.** For any integer $k \ge 3$ and thin and thick headless spiders $H_k$ and $\overline{H}_k$, respectively, we have $\gamma^{\text{OSD}}(H_k) = k$ and $\gamma^{\text{OSD}}(\overline{H}_k) = k+1$.

Hence, Lemma 4 combined with the results from [3] show that for the thin and the thick headless spiders $H_k$ and $\overline{H}_k$, respectively, the OSD- and the OLD-numbers are equal for all $k \ge 3$. It would be interesting to study whether there exist families of open twin-free split graphs where the OSD- and the OLD-numbers differ.

*Thin suns.* The latter result on thin headless spiders can be further generalized to thin suns. A *sun* is a graph $G = (C \cup S, E)$ whose vertex set can be partitioned into $S$ and $C$, where, for an integer $k \ge 3$, the set $S = \{s_1, \dots, s_k\}$ is a stable

<figure><img src="image_4.png" /><figcaption>Fig. 3: Split graphs (the black vertices belong to $Q$ and the white vertices to $S$), where (a) is the $P_4$, (b) the gem, (c) the net, (d) the sun.</figcaption></figure>
**Lemma 3.** For a $k$-double star $D_k$ with $k \ge 2$, we have $\gamma^{\text{OSD}}(D_k) = 2k-1$ and $\gamma^{\text{OLD}}(D_k) = 2k$.

*Split graphs.* A graph $G = (Q \cup S, E)$ is a split graph if its vertex set can be partitioned into a clique $Q$ and a stable set $S$. In order to study OSD-codes of split graphs and compare them with the OLD-codes, we restrict ourselves to split graphs $G$ without open twins and isolated vertices. This further implies that $G$ is connected and $Q$ non-empty (as, otherwise, every component not containing the clique $Q$ needs to be an isolated vertex from $S$, contradicting our assumptions). Figure 3 shows some small OLD-admissible graphs. It is easy to see that $\gamma^{\text{OSD}}(G)$ and $\gamma^{\text{OLD}}(G)$ differ for $G \in \{P_4, \text{gem}\}$ and are equal for $G \in \{\text{net, sun}\}$.

We next examine OSD-codes in two families of split graphs for which the exact OLD-numbers are known from [3]. A headless spider is a split graph with $Q = \{q_1, \dots, q_k\}$ and $S = \{s_1, \dots, s_k\}$. In addition, a headless spider is thin (respectively, thick) if $s_i$ is adjacent to $q_j$ if and only if $i = j$ (respectively, $i \neq j$). By definition, it is clear that the complement of a thin headless spider $H_k$ is a thick headless spider $\overline{H}_k$, and vice-versa. We have $H_2 = \overline{H}_2 = P_4$, the two headless spiders $H_3 = \text{net}$ and $\overline{H}_3 = \text{sun}$ are depicted in Figures 3(c) and 3(d), respectively. Moreover, it is easy to check that the thin and the thick headless spiders have no twins.

In [3], it was shown that $\gamma^{\text{OLD}}(H_k) = k$ for $k \ge 3$ and $\gamma^{\text{OLD}}(\overline{H}_k) = k+1$ for $k \ge 3$. We next analyse the OSD-numbers of the thin and the thick headless spiders.

**Lemma 4.** For any integer $k \ge 3$ and thin and thick headless spiders $H_k$ and $\overline{H}_k$, respectively, we have $\gamma^{\text{OSD}}(H_k) = k$ and $\gamma^{\text{OSD}}(\overline{H}_k) = k+1$.

Hence, Lemma 4 combined with the results from [3] show that for the thin and the thick headless spiders $H_k$ and $\overline{H}_k$, respectively, the OSD- and the OLD-numbers are equal for all $k \ge 3$. It would be interesting to study whether there exist families of open twin-free split graphs where the OSD- and the OLD-numbers differ.

*Thin suns.* The latter result on thin headless spiders can be further generalized to thin suns. A sun is a graph $G = (C \cup S, E)$ whose vertex set can be partitioned into $S$ and $C$, where, for an integer $k \ge 3$, the set $S = \{s_1, \dots, s_k\}$ is a stable

<figure><img src="image_4.png" /><figcaption>Fig. 3: Split graphs (the black vertices belong to $Q$ and the white vertices to $S$), where (a) is the $P_4$, (b) the gem, (c) the net, (d) the sun.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 4: The three thin suns $T_4$ where (a) is a sunlet and (c) a thin headless spider.</figcaption></figure>

set and $C = \{c_1, \dots, c_k\}$ is a (not necessarily chordless) cycle. A thin sun $T_k = (C \cup S, E)$ is a sun where $s_i$ is adjacent to $c_j$ if and only if $i = j$. Therefore, thin headless spiders are special thin suns where all chords of the cycle $C$ are present (such that $C$ induces a clique). Other special cases of thin suns are sunlets where no chords of the cycle $C$ are present (such that $C$ induces a hole). For illustration, for $k=3$, the (only) thin sun $T_3$ equals the thin headless spider $H_3$ (see Figure 3(c)); for $k=4$, the three possible thin suns $T_4$ are depicted in Figure 4.

We call two vertices $c_i$ and $c_j$ of a thin sun $T_k = (C \cup S, E)$ open $C$-twins if $c_i$ and $c_j$ are non-adjacent and $N_C(c_i) = N_C(c_j)$, where $N_C(v) = N(v) \cap C$. For instance, the sunlet in Figure 4(a) and the thin sun in Figure 4(b) have open $C$-twins, whereas the thin headless spider in Figure 4(c) does not.

In [3], it was shown that for a thin sun $T_k$ with $k \ge 4$ and without open $C$-twins, the set $C$ is the unique minimum OSD-code of $T_k$ and thus, we have $\gamma^{\text{OLD}}(T_k) = k$. Now, with regards to OSD-numbers of thin suns, we show the following.

**Lemma 5.** For a thin sun $T_k = (C \cup S, E)$ with $k \ge 4$ and without open $C$-twins, $C$ is a minimum OSD-code and hence, we have $\gamma^{\text{OSD}}(T_k) = |C| = k$.

Therefore, thin suns without open $C$-twins are examples of graphs where the OSD- and the OLD-number are equal. This applies in particular to sunlets $T_k$ with $k \ge 5$ and to thin headless spiders. However, for thin suns $T_k$ with open $C$-twins, $\gamma^{\text{OSD}}(T_k)$ and $\gamma^{\text{OLD}}(T_k)$ may differ. For instance, for the thin sun $T_4$ depicted in Fig. 4(b), it can be checked that $\gamma^{\text{OSD}}(T_4) = 4 < 5 = \gamma^{\text{OLD}}(T_4)$. We call a thin sun $T_k = (C \cup S, E)$ almost complete if $k = 2\ell$ and $c_i$ is non-adjacent to $c_{i+\ell}$ but is adjacent to all other $c_j \in C$. We can show:

**Lemma 6.** For an almost complete thin sun $T_{2\ell}$ with $\ell \ge 3$, we have $\gamma^{\text{OSD}}(T_{2\ell}) = 3\ell - 1$ and $\gamma^{\text{OLD}}(T_{2\ell}) = 3\ell$.

Hence, there exist infinitely many thin suns with open $C$-twins for which the OSD- and the OLD-numbers differ.
<figure><img src="image_5.png" /><figcaption>Fig. 4: The three thin suns $T_4$ where (a) is a sunlet and (c) a thin headless spider.</figcaption></figure>

set and $C = \{c_1, \dots, c_k\}$ is a (not necessarily chordless) cycle. A thin sun $T_k = (C \cup S, E)$ is a sun where $s_i$ is adjacent to $c_j$ if and only if $i = j$. Therefore, thin headless spiders are special thin suns where all chords of the cycle $C$ are present (such that $C$ induces a clique). Other special cases of thin suns are sunlets where no chords of the cycle $C$ are present (such that $C$ induces a hole). For illustration, for $k=3$, the (only) thin sun $T_3$ equals the thin headless spider $H_3$ (see Figure 3(c)); for $k=4$, the three possible thin suns $T_4$ are depicted in Figure 4.

We call two vertices $c_i$ and $c_j$ of a thin sun $T_k = (C \cup S, E)$ open $C$-twins if $c_i$ and $c_j$ are non-adjacent and $N_C(c_i) = N_C(c_j)$, where $N_C(v) = N(v) \cap C$. For instance, the sunlet in Figure 4(a) and the thin sun in Figure 4(b) have open $C$-twins, whereas the thin headless spider in Figure 4(c) does not.

In [3], it was shown that for a thin sun $T_k$ with $k \ge 4$ and without open $C$-twins, the set $C$ is the unique minimum OSD-code of $T_k$ and thus, we have $\gamma^{\text{OLD}}(T_k) = k$. Now, with regards to OSD-numbers of thin suns, we show the following.

**Lemma 5.** For a thin sun $T_k = (C \cup S, E)$ with $k \ge 4$ and without open $C$-twins, $C$ is a minimum OSD-code and hence, we have $\gamma^{\text{OSD}}(T_k) = |C| = k$.

Therefore, thin suns without open $C$-twins are examples of graphs where the OSD- and the OLD-number are equal. This applies in particular to sunlets $T_k$ with $k \ge 5$ and to thin headless spiders. However, for thin suns $T_k$ with open $C$-twins, $\gamma^{\text{OSD}}(T_k)$ and $\gamma^{\text{OLD}}(T_k)$ may differ. For instance, for the thin sun $T_4$ depicted in Fig. 4(b), it can be checked that $\gamma^{\text{OSD}}(T_4) = 4 < 5 = \gamma^{\text{OLD}}(T_4)$. We call a thin sun $T_k = (C \cup S, E)$ almost complete if $k = 2\ell$ and $c_i$ is non-adjacent to $c_{i+\ell}$ but is adjacent to all other $c_j \in C$. We can show:

**Lemma 6.** For an almost complete thin sun $T_{2\ell}$ with $\ell \ge 3$, we have $\gamma^{\text{OSD}}(T_{2\ell}) = 3\ell - 1$ and $\gamma^{\text{OLD}}(T_{2\ell}) = 3\ell$.

Hence, there exist infinitely many thin suns with open $C$-twins for which the OSD- and the OLD-numbers differ.
# 4 Polyhedra associated with OSD-codes

As polyhedral methods turned out to be successful for many NP-hard combinatorial optimization problems in the literature, it was suggested in [2,3] to apply such techniques to locating-dominating type problems. For that, a reformulation of the studied X-problem in a graph $G$ as a covering problem in a suitable hypergraph $\mathcal{H}_X(G)$ is in order. The incidence matrix of $\mathcal{H}_X(G)$ then defines the constraint system of the resulting covering problem. We next study the OSD-codes in this context.

*Hypergraph representation of the OSD-problem.* Given a graph $G = (V, E)$ and a problem $X$, we look for a hypergraph $\mathcal{H}_X(G) = (V, \mathcal{F}_X)$ so that $C \subset V$ is an X-code of $G$ if and only if $C$ is a cover of $\mathcal{H}_X(G)$ satisfying $C \cap F \neq \emptyset$ for all $F \in \mathcal{F}_X$. Then the covering number $\tau(\mathcal{H}_X(G))$, defined as the minimum cardinality of a cover of $\mathcal{H}_X(G)$, equals by construction the X-number $\gamma^X(G)$ of $G$. The hypergraph $\mathcal{H}_X(G)$ is called the X-hypergraph of the graph $G$.

It is a simple observation that for an X-problem involving domination (respectively, total-domination), $\mathcal{F}_X$ needs to contain the closed (respectively, open) neighborhoods of all vertices of $G$. In order to encode the separation of vertices, that is, the fact that the intersections of an X-code $C$ with the neighborhood of each vertex is unique, it was suggested in [2,3] to use the symmetric differences of the neighborhoods. Here, given two sets $A$ and $B$, their symmetric difference is defined by $A\Delta B = (A \setminus B) \cup (B \setminus A)$. In fact, it has been shown in [2,3] that a code $C$ of a graph $G$ is closed-separating (respectively, open-separating) if and only if $(N[u]\Delta N[v]) \cap C \neq \emptyset$ (respectively, $(N(u)\Delta N(v)) \cap C \neq \emptyset$) for all pairs of distinct vertices $u, v$ of $G$. This implies for OSD-codes:

**Corollary 3.** The OSD-hypergraph $\mathcal{H}_{\text{OSD}}(G) = (V, \mathcal{F}_{\text{OSD}})$ of a graph $G = (V, E)$ is composed of

- the closed neighborhoods $N[v]$ of all vertices $v \in V$ and

- the symmetric differences $N(u)\Delta N(v)$ of open neighborhoods of distinct vertices $u, v \in V$

as hyperedges in $\mathcal{F}_{\text{OSD}}$ and $\gamma^{\text{OSD}}(G) = \tau(\mathcal{H}_{\text{OSD}}(G))$ holds.

Note that a graph $G = (V, E)$ is not X-admissible if there is $\emptyset \in \mathcal{F}_X$ as then there is no $C \subset V$ satisfying $F \cap C \neq \emptyset$ for all $F \in \mathcal{F}_X$. For OSD-codes, we see that $N(u)\Delta N(v) = \emptyset$ whenever $u, v$ are open twins, again showing that only open twin-free graphs are OSD-admissible.

It was observed in [2,3] that $\mathcal{H}_X(G) = (V, \mathcal{F}_X)$ may contain redundant hyperedges. In fact, if there are two hyperedges $F, F' \in \mathcal{F}_X$ with $F \subset F'$, then $F \cap C \neq \emptyset$ also implies $F' \cap C \neq \emptyset$ for every $C \subset V$. Thus, $F'$ is redundant as $(V, \mathcal{F}_X - \{F'\})$ suffices to encode the domination and separation properties of the X-codes of $G$. This motivates to consider the X-clutter $\mathcal{C}_X(G)$ of the graph $G$ obtained from $\mathcal{H}_X(G)$ by removing all redundant hyperedges of the latter. We note that clearly $\tau(\mathcal{H}_{\text{OSD}}(G)) = \tau(\mathcal{C}_{\text{OSD}}(G))$ holds.
# 4 Polyhedra associated with OSD-codes

As polyhedral methods turned out to be successful for many NP-hard combinatorial optimization problems in the literature, it was suggested in [2,3] to apply such techniques to locating-dominating type problems. For that, a reformulation of the studied X-problem in a graph $G$ as a covering problem in a suitable hypergraph $\mathcal{H}_X(G)$ is in order. The incidence matrix of $\mathcal{H}_X(G)$ then defines the constraint system of the resulting covering problem. We next study the OSD-codes in this context.

*Hypergraph representation of the OSD-problem.* Given a graph $G = (V, E)$ and a problem $X$, we look for a hypergraph $\mathcal{H}_X(G) = (V, \mathcal{F}_X)$ so that $C \subset V$ is an X-code of $G$ if and only if $C$ is a cover of $\mathcal{H}_X(G)$ satisfying $C \cap F \neq \emptyset$ for all $F \in \mathcal{F}_X$. Then the covering number $\tau(\mathcal{H}_X(G))$, defined as the minimum cardinality of a cover of $\mathcal{H}_X(G)$, equals by construction the X-number $\gamma^X(G)$ of $G$. The hypergraph $\mathcal{H}_X(G)$ is called the X-hypergraph of the graph $G$.

It is a simple observation that for an X-problem involving domination (respectively, total-domination), $\mathcal{F}_X$ needs to contain the closed (respectively, open) neighborhoods of all vertices of $G$. In order to encode the separation of vertices, that is, the fact that the intersections of an X-code $C$ with the neighborhood of each vertex is unique, it was suggested in [2,3] to use the symmetric differences of the neighborhoods. Here, given two sets $A$ and $B$, their symmetric difference is defined by $A\Delta B = (A \setminus B) \cup (B \setminus A)$. In fact, it has been shown in [2,3] that a code $C$ of a graph $G$ is closed-separating (respectively, open-separating) if and only if $(N[u]\Delta N[v]) \cap C \neq \emptyset$ (respectively, $(N(u)\Delta N(v)) \cap C \neq \emptyset$) for all pairs of distinct vertices $u, v$ of $G$. This implies for OSD-codes:

**Corollary 3.** The OSD-hypergraph $\mathcal{H}_{\text{OSD}}(G) = (V, \mathcal{F}_{\text{OSD}})$ of a graph $G = (V, E)$ is composed of

- the closed neighborhoods $N[v]$ of all vertices $v \in V$ and

- the symmetric differences $N(u)\Delta N(v)$ of open neighborhoods of distinct vertices $u, v \in V$

as hyperedges in $\mathcal{F}_{\text{OSD}}$ and $\gamma^{\text{OSD}}(G) = \tau(\mathcal{H}_{\text{OSD}}(G))$ holds.

Note that a graph $G = (V, E)$ is not X-admissible if there is $\emptyset \in \mathcal{F}_X$ as then there is no $C \subset V$ satisfying $F \cap C \neq \emptyset$ for all $F \in \mathcal{F}_X$. For OSD-codes, we see that $N(u)\Delta N(v) = \emptyset$ whenever $u, v$ are open twins, again showing that only open twin-free graphs are OSD-admissible.

It was observed in [2,3] that $\mathcal{H}_X(G) = (V, \mathcal{F}_X)$ may contain redundant hyperedges. In fact, if there are two hyperedges $F, F' \in \mathcal{F}_X$ with $F \subset F'$, then $F \cap C \neq \emptyset$ also implies $F' \cap C \neq \emptyset$ for every $C \subset V$. Thus, $F'$ is redundant as $(V, \mathcal{F}_X - \{F'\})$ suffices to encode the domination and separation properties of the X-codes of $G$. This motivates to consider the X-clutter $\mathcal{C}_X(G)$ of the graph $G$ obtained from $\mathcal{H}_X(G)$ by removing all redundant hyperedges of the latter. We note that clearly $\tau(\mathcal{H}_{\text{OSD}}(G)) = \tau(\mathcal{C}_{\text{OSD}}(G))$ holds.
Moreover, a special interest lies in hyperedges of $C_X(G)$ consisting of a single vertex, called the *forced vertex*, as each forced vertex needs to belong to every X-code of $G$. For OSD-codes, we denote the set of forced vertices of $G$ by $\mathcal{F}_{\text{OSD}}^1(G)$ and can characterise them in the following manner.

**Lemma 7.** For an OSD-admissible graph $G$, we have $\mathcal{F}_{\text{OSD}}^1(G) = V_0 \cup V_1$, where

$$ 
\begin{aligned}
V_0 &= \{x \in V : N(x) = \emptyset\}; \quad \text{and} \\
V_1 &= \{y \in V : \exists \text{ non-adjacent } u, v \text{ with } \{y\} = N(u)\Delta N(v)\}.
\end{aligned}
$$

Note that for an OSD-admissible graph $G$ having an isolated vertex $v$, $V_1$ contains all vertices $u$ of degree 1 (as $N(u)\Delta N(v) = N(u)\Delta \emptyset = N(u)$ holds). Accordingly, we express the OSD-clutter of a graph $G = (V, E)$ by $C_{\text{OSD}}(G) = (V, \mathcal{F}_{\text{OSD}}^1(G) \cup \mathcal{F}_{\text{OSD}}^2(G))$, where $\mathcal{F}_{\text{OSD}}^2(G)$ is composed of all non-redundant hyperedges of $\mathcal{H}_{\text{OSD}}(G)$ with size at least 2. For illustration, we construct $\mathcal{H}_{\text{OSD}}(P_4)$ and $C_{\text{OSD}}(P_4)$. The OSD-hypergraph $\mathcal{H}_{\text{OSD}}(P_4)$ is composed of

$$ 
\begin{aligned}
N[1] &= \{1, 2\} & N(1)\Delta N(2) &= \{1, 2, 3\} & N(1)\Delta N(3) &= \{4\} \\
N[2] &= \{1, 2, 3\} & N(2)\Delta N(3) &= \{1, 2, 3, 4\} & N(1)\Delta N(4) &= \{2, 3\} \\
N[3] &= \{2, 3, 4\} & N(3)\Delta N(4) &= \{2, 3, 4\} & N(2)\Delta N(4) &= \{1\} \\
N[4] &= \{3, 4\}
\end{aligned}
$$

Clearly, the OSD-clutter $C_{\text{OSD}}(P_4)$ only contains the symmetric differences of open neighborhoods of non-adjacent vertices, namely, the sets $\{1\}, \{2, 3\}, \{4\}$. Moreover, we have $\mathcal{F}_{\text{OSD}}^1(P_4) = \{1, 4\}$ and $\mathcal{F}_{\text{OSD}}^2(P_4) = \{\{2, 3\}\}$. Note that for the previously studied X-problems, it has been shown in [2, 3] that $C_X(G)$ does not contain symmetric differences of neighborhoods of non-adjacent vertices without common neighbor. This does not apply to OSD-clutters, as $N(1)\Delta N(4) = \{2, 3\}$ from the above example demonstrates.

*Polyhedra associated with OSD-codes.* Due to $\gamma^{\text{OSD}}(G) = \tau(C_{\text{OSD}}(G))$, we can determine a minimum OSD-code in a graph $G = (V, E)$ by solving the following covering problem

$$ 
\begin{array}{l}
\min \mathbf{1}^T \mathbf{x} \\
M_{\text{OSD}}(G) \quad \mathbf{x} \ge \mathbf{1} \\
\mathbf{x} \in \{0, 1\}^{|V|}
\end{array}
$$

where **1** is the vector having 1-entries only and $M_{\text{OSD}}(G)$ is the incidence matrix of the OSD-clutter $C_{\text{OSD}}(G)$ encoding row-wise its hyperedges $F$ (that is, the row of $M_{\text{OSD}}(G)$ corresponding to $F$ is a 0/1-vector of length $|V|$ having a 1-entry if $v \in F$ and a 0-entry otherwise). For any 0/1-matrix $M$ with $n$ columns, the associated covering polyhedron is $P(M) = \text{conv}\{\mathbf{x} \in \mathbb{Z}_+^n : M\mathbf{x} \ge \mathbf{1}\}$. Accordingly, the OSD-polyhedron of $G = (V, E)$ is defined by

$$ P_{\text{OSD}}(G) = P(M_{\text{OSD}}(G)) = \text{conv}\{\mathbf{x} \in \mathbb{Z}_+^{|V|} : M_{\text{OSD}}(G) \mathbf{x} \ge \mathbf{1}\}. $$

Based on results from [5] on general covering polyhedra, we prove the following.
Moreover, a special interest lies in hyperedges of $C_X(G)$ consisting of a single vertex, called the *forced vertex*, as each forced vertex needs to belong to every X-code of $G$. For OSD-codes, we denote the set of forced vertices of $G$ by $\mathcal{F}_{\text{OSD}}^1(G)$ and can characterise them in the following manner.

**Lemma 7.** For an OSD-admissible graph $G$, we have $\mathcal{F}_{\text{OSD}}^1(G) = V_0 \cup V_1$, where

$$ 
\begin{aligned}
V_0 &= \{x \in V : N(x) = \emptyset\}; \quad \text{and} \\
V_1 &= \{y \in V : \exists \text{ non-adjacent } u, v \text{ with } \{y\} = N(u)\Delta N(v)\}.
\end{aligned}
$$

Note that for an OSD-admissible graph $G$ having an isolated vertex $v$, $V_1$ contains all vertices $u$ of degree 1 (as $N(u)\Delta N(v) = N(u)\Delta \emptyset = N(u)$ holds). Accordingly, we express the OSD-clutter of a graph $G = (V, E)$ by $C_{\text{OSD}}(G) = (V, \mathcal{F}_{\text{OSD}}^1(G) \cup \mathcal{F}_{\text{OSD}}^2(G))$, where $\mathcal{F}_{\text{OSD}}^2(G)$ is composed of all non-redundant hyperedges of $\mathcal{H}_{\text{OSD}}(G)$ with size at least 2. For illustration, we construct $\mathcal{H}_{\text{OSD}}(P_4)$ and $C_{\text{OSD}}(P_4)$. The OSD-hypergraph $\mathcal{H}_{\text{OSD}}(P_4)$ is composed of

$$ 
\begin{aligned}
N[1] &= \{1, 2\} & N(1)\Delta N(2) &= \{1, 2, 3\} & N(1)\Delta N(3) &= \{4\} \\
N[2] &= \{1, 2, 3\} & N(2)\Delta N(3) &= \{1, 2, 3, 4\} & N(1)\Delta N(4) &= \{2, 3\} \\
N[3] &= \{2, 3, 4\} & N(3)\Delta N(4) &= \{2, 3, 4\} & N(2)\Delta N(4) &= \{1\} \\
N[4] &= \{3, 4\}
\end{aligned}
$$

Clearly, the OSD-clutter $C_{\text{OSD}}(P_4)$ only contains the symmetric differences of open neighborhoods of non-adjacent vertices, namely, the sets $\{1\}, \{2, 3\}, \{4\}$. Moreover, we have $\mathcal{F}_{\text{OSD}}^1(P_4) = \{1, 4\}$ and $\mathcal{F}_{\text{OSD}}^2(P_4) = \{\{2, 3\}\}$. Note that for the previously studied X-problems, it has been shown in [2, 3] that $C_X(G)$ does not contain symmetric differences of neighborhoods of non-adjacent vertices without common neighbor. This does not apply to OSD-clutters, as $N(1)\Delta N(4) = \{2, 3\}$ from the above example demonstrates.

*Polyhedra associated with OSD-codes.* Due to $\gamma^{\text{OSD}}(G) = \tau(C_{\text{OSD}}(G))$, we can determine a minimum OSD-code in a graph $G = (V, E)$ by solving the following covering problem

$$ 
\begin{array}{ll}
\min & \mathbf{1}^T \mathbf{x} \\
M_{\text{OSD}}(G) & \mathbf{x} \ge \mathbf{1} \\
& \mathbf{x} \in \{0, 1\}^{|V|}
\end{array}
$$

where $\mathbf{1}$ is the vector having 1-entries only and $M_{\text{OSD}}(G)$ is the incidence matrix of the OSD-clutter $C_{\text{OSD}}(G)$ encoding row-wise its hyperedges $F$ (that is, the row of $M_{\text{OSD}}(G)$ corresponding to $F$ is a 0/1-vector of length $|V|$ having a 1-entry if $v \in F$ and a 0-entry otherwise). For any 0/1-matrix $M$ with $n$ columns, the associated covering polyhedron is $P(M) = \text{conv}\{\mathbf{x} \in \mathbb{Z}_+^n : M\mathbf{x} \ge \mathbf{1}\}$. Accordingly, the OSD-polyhedron of $G = (V, E)$ is defined by

$$ P_{\text{OSD}}(G) = P(M_{\text{OSD}}(G)) = \text{conv}\{\mathbf{x} \in \mathbb{Z}_+^{|V|} : M_{\text{OSD}}(G) \mathbf{x} \ge \mathbf{1}\}. $$

Based on results from [5] on general covering polyhedra, we prove the following.
**Theorem 5.** Let $G = (V, E)$ be an OSD-admissible graph. $P_{\text{OSD}}(G)$ has

(a) the equation $x_v = 1$ for all forced vertices $v \in \mathcal{F}_{\text{OSD}}^{1}(G)$;

(b) a nonnegativity constraint $x_v \ge 0$ for all vertices $v \notin \mathcal{F}_{\text{OSD}}^{1}(G)$ and

(c) $\sum_{v \in F} x_v \ge 1$ for all hyperedges $F$ of $\mathcal{C}_{\text{OSD}}(G)$ with $F \in \mathcal{F}_{\text{OSD}}^{2}(G)$.

For any covering polyhedron $P(M)$ associated with a 0/1-matrix $M$ with $n$ columns, $Q(M) = \{\mathbf{x} \in \mathbb{R}_{+}^{n} : M\mathbf{x} \ge \mathbf{1}\}$ is its linear relaxation. We have $P(M) \subseteq Q(M)$ in general and further constraints have to be added to the system $M\mathbf{x} \ge \mathbf{1}$ in order to describe $P(M)$ using real variables instead of integral ones.

We next study the OSD-polyhedra for some special graphs related to hyper-graph $\mathcal{R}_n^q = (V, \mathcal{E})$ called complete $q$-rose of order $n$, where $V = \{1, \dots, n\}$ and $\mathcal{E}$ contains all $q$-element subsets of $V$ for $2 \le q < n$. In [2] it was proved that the covering polyhedron of $\mathcal{R}_n^q$ is given by the nonnegativity constraints and

$$x(V') = \sum_{v \in V'} x_v \ge |V'| - q + 1$$

for all subsets $V' \subseteq \{1, \dots, n\}$ with $|V'| \in \{q, \dots, n\}$. Moreover, we have $\tau(\mathcal{R}_n^q) = n - q + 1$. Note that, for $q = 2$, $\mathcal{R}_n^q$ is in fact the complete graph $K_n$.

Determining the OSD-clutters of the graph families studied below showed their relation to different complete $q$-roses. Relying on the results from [2] on polyhedra associated to complete $q$-roses enabled us to prove the following.

**Theorem 6.** Let $G = (V, E)$ be either a clique $K_n$ with $n \ge 2$ or a matching $kK_2$ with $k \ge 1$ and $n = 2k$. Then, we have $\mathcal{C}_{\text{OSD}}(G) = \mathcal{R}_n^2 = K_n$ and $P_{\text{OSD}}(G)$ is given by

(a) a nonnegativity constraint $x_v \ge 0$ for all vertices $v \in V$ and

(b) $x(V') = \sum_{v \in V'} x_v \ge |V'| - 1$ for all subsets $V' \subseteq V$ with $|V'| \ge 2$.

Note that two graphs with equal OSD-clutters have the same set of OSD-codes and thus also the same OSD-numbers and the same OSD-polyhedra. Theorem 6 shows that this applies to cliques and matchings. The following two theorems show that the OSD-numbers of thin and thick headless spiders, as calculated in Lemma 4, can also be arrived by the use of polyhedral techniques.

**Theorem 7.** Let $\bar{H}_k = (Q \cup S, E)$ be a thick headless spider with $k \ge 4$. Then, we have $\mathcal{C}_{\text{OSD}}(\bar{H}_k) = \mathcal{R}_{|S|}^{S|-1} \cup \mathcal{R}_{|Q|}^2$ and $P_{\text{OSD}}(\bar{H}_k)$ is given by the constraints

(a) $x_v \ge 0$ for all vertices $v \in Q \cup S$,

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

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

Comparing this result with the result from [3] on OLD-codes of thick headless spiders, we observe that $\mathcal{C}_{\text{OSD}}(\bar{H}_k) = \mathcal{C}_{\text{OLD}}(\bar{H}_k)$. Hence, a vertex subset is an OSD-code of $\bar{H}_k$ if and only if it is an OLD-code of $\bar{H}_k$. Accordingly, the OSD- and the OLD-numbers and as well as the OSD- and the OLD-polyhedra are equal for thick headless spiders.
**Theorem 5.** Let $G = (V, E)$ be an OSD-admissible graph. $P_{\text{OSD}}(G)$ has

(a) the equation $x_v = 1$ for all forced vertices $v \in \mathcal{F}_{\text{OSD}}^{1}(G)$;

(b) a nonnegativity constraint $x_v \ge 0$ for all vertices $v \notin \mathcal{F}_{\text{OSD}}^{1}(G)$ and

(c) $\sum_{v \in F} x_v \ge 1$ for all hyperedges $F$ of $\mathcal{C}_{\text{OSD}}(G)$ with $F \in \mathcal{F}_{\text{OSD}}^{2}(G)$.

For any covering polyhedron $P(M)$ associated with a 0/1-matrix $M$ with $n$ columns, $Q(M) = \{\mathbf{x} \in \mathbb{R}_+^n : M\mathbf{x} \ge \mathbf{1}\}$ is its linear relaxation. We have $P(M) \subseteq Q(M)$ in general and further constraints have to be added to the system $M\mathbf{x} \ge \mathbf{1}$ in order to describe $P(M)$ using real variables instead of integral ones.

We next study the OSD-polyhedra for some special graphs related to hypergraph $\mathcal{R}_n^q = (V, \mathcal{E})$ called complete $q$-rose of order $n$, where $V = \{1, \dots, n\}$ and $\mathcal{E}$ contains all $q$-element subsets of $V$ for $2 \le q < n$. In [2] it was proved that the covering polyhedron of $\mathcal{R}_n^q$ is given by the nonnegativity constraints and

$$x(V') = \sum_{v \in V'} x_v \ge |V'| - q + 1$$

for all subsets $V' \subseteq \{1, \dots, n\}$ with $|V'| \in \{q, \dots, n\}$. Moreover, we have $\tau(\mathcal{R}_n^q) = n - q + 1$. Note that, for $q = 2$, $\mathcal{R}_n^q$ is in fact the complete graph $K_n$.

Determining the OSD-clutters of the graph families studied below showed their relation to different complete $q$-roses. Relying on the results from [2] on polyhedra associated to complete $q$-roses enabled us to prove the following.

**Theorem 6.** Let $G = (V, E)$ be either a clique $K_n$ with $n \ge 2$ or a matching $kK_2$ with $k \ge 1$ and $n = 2k$. Then, we have $\mathcal{C}_{\text{OSD}}(G) = \mathcal{R}_n^2 = K_n$ and $P_{\text{OSD}}(G)$ is given by

(a) a nonnegativity constraint $x_v \ge 0$ for all vertices $v \in V$ and

(b) $x(V') = \sum_{v \in V'} x_v \ge |V'| - 1$ for all subsets $V' \subseteq V$ with $|V'| \ge 2$.

Note that two graphs with equal OSD-clutters have the same set of OSD-codes and thus also the same OSD-numbers and the same OSD-polyhedra. Theorem 6 shows that this applies to cliques and matchings. The following two theorems show that the OSD-numbers of thin and thick headless spiders, as calculated in Lemma 4, can also be arrived by the use of polyhedral techniques.

**Theorem 7.** Let $\bar{H}_k = (Q \cup S, E)$ be a thick headless spider with $k \ge 4$. Then, we have $\mathcal{C}_{\text{OSD}}(\bar{H}_k) = \mathcal{R}_{|S|}^{S|-1} \cup \mathcal{R}_{|Q|}^2$ and $P_{\text{OSD}}(\bar{H}_k)$ is given by the constraints

(a) $x_v \ge 0$ for all vertices $v \in Q \cup S$,

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

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

Comparing this result with the result from [3] on OLD-codes of thick headless spiders, we observe that $\mathcal{C}_{\text{OSD}}(\bar{H}_k) = \mathcal{C}_{\text{OLD}}(\bar{H}_k)$. Hence, a vertex subset is an OSD-code of $\bar{H}_k$ if and only if it is an OLD-code of $\bar{H}_k$. Accordingly, the OSD- and the OLD-numbers and as well as the OSD- and the OLD-polyhedra are equal for thick headless spiders.
**Theorem 8.** Consider a thin headless spider $H_k = (Q \cup S, E)$ with $k \ge 4$. Then, we have $C_{\text{OSD}}(H_k) = H_k$ and $P_{\text{OSD}}(H_k)$ is given by the constraints

(a) $x_v \ge 0$ for all vertices $v \in Q \cup S$,

(b) $x_{q_i} + x_{s_i} \ge 1$ for $1 \le i \le k$,

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

Combining all the constraints in (b) yields $x(Q) + x(S) \ge k$ and this implies $\gamma^{\text{OSD}}(H_k) \ge k$. It is also easy to see that $Q$ is a cover of $C_{\text{OSD}}(H_k)$ and hence, $\gamma^{\text{OSD}}(H_k) = k$. This illustrates how, on the one hand, polyhedral arguments can be used to determine lower bounds for OSD-numbers and, on the other hand, an analysis of the OSD-clutter provides OSD-codes. Moreover, if the order of the latter meets the lower bound, the OSD-number of the studied graph is determined.

We note further that manifold hypergraphs have been already studied in the covering context, see e.g. [1, 9, 14] to mention just a few. The same techniques as illustrated above with the help of complete $q$-roses can be applied whenever the OSD-clutter of some graph equals such a hypergraph or contains such a hypergraph as substructure, which gives an interesting perspective of studying OSD-polyhedra further.

# 5 Concluding remarks

In this paper, we introduced and studied open-separating dominating codes in graphs. We showed that such codes exist in graphs without open twins and that finding minimum OSD-codes is NP-hard. Moreover, we provided bounds on the OSD-number of a graph both in terms of its number of vertices and in relation to other X-numbers, notably showing that OSD- and OLD-number of a graph differ by at most one. Despite this closeness between the OSD- and the OLD-numbers, we proved that it is NP-complete to decide if the two said parameters of a graph actually differ. This further motivated us to compare the two numbers on several graph families. This study revealed that they

- are equal, for example, for cliques $K_n$ with $n \ge 3$, thin and thick headless spiders $H_k$ and $\bar{H}_k$, respectively, with $k \ge 3$, and thin sums $T_k = (C \cup S, E)$ with $k \ge 4$ and without open C-twins;

- differ for example, for matchings $kK_2$ with $k \ge 1$, half-graphs $B_k$ with $k \ge 1$ and their disjoint unions, $k$-double stars $D_k$ with $n \ge 2$, and almost complete thin sums $T_{2\ell}$ with $\ell \ge 3$.

In particular, this showed that the OSD-numbers of cliques, half-graphs and their disjoint unions attain the upper bound in Theorem 1. Moreover, we provided an equivalent reformulation of the OSD-problem as a covering problem in a suitable hypergraph composed of the closed neighborhoods and the symmetric differences of open neighborhoods of vertices. We also discussed the polyhedra associated with the OSD-codes, particularly, in relation to the OLD-codes of some graph families already studied in this context. The latter illustrated how polyhedral
**Theorem 8.** Consider a thin headless spider $H_k = (Q \cup S, E)$ with $k \ge 4$. Then, we have $C_{\text{OSD}}(H_k) = H_k$ and $P_{\text{OSD}}(H_k)$ is given by the constraints

(a) $x_v \ge 0$ for all vertices $v \in Q \cup S$,

(b) $x_{q_i} + x_{s_i} \ge 1$ for $1 \le i \le k$,

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

Combining all the constraints in (b) yields $x(Q) + x(S) \ge k$ and this implies $\gamma^{\text{OSD}}(H_k) \ge k$. It is also easy to see that $Q$ is a cover of $C_{\text{OSD}}(H_k)$ and hence, $\gamma^{\text{OSD}}(H_k) = k$. This illustrates how, on the one hand, polyhedral arguments can be used to determine lower bounds for OSD-numbers and, on the other hand, an analysis of the OSD-clutter provides OSD-codes. Moreover, if the order of the latter meets the lower bound, the OSD-number of the studied graph is determined.

We note further that manifold hypergraphs have been already studied in the covering context, see e.g. [1, 9, 14] to mention just a few. The same techniques as illustrated above with the help of complete $q$-roses can be applied whenever the OSD-clutter of some graph equals such a hypergraph or contains such a hypergraph as substructure, which gives an interesting perspective of studying OSD-polyhedra further.

# 5 Concluding remarks

In this paper, we introduced and studied open-separating dominating codes in graphs. We showed that such codes exist in graphs without open twins and that finding minimum OSD-codes is NP-hard. Moreover, we provided bounds on the OSD-number of a graph both in terms of its number of vertices and in relation to other X-numbers, notably showing that OSD- and OLD-number of a graph differ by at most one. Despite this closeness between the OSD- and the OLD-numbers, we proved that it is NP-complete to decide if the two said parameters of a graph actually differ. This further motivated us to compare the two numbers on several graph families. This study revealed that they

- are equal, for example, for cliques $K_n$ with $n \ge 3$, thin and thick headless spiders $H_k$ and $\bar{H}_k$, respectively, with $k \ge 3$, and thin sums $T_k = (C \cup S, E)$ with $k \ge 4$ and without open C-twins;

- differ for example, for matchings $kK_2$ with $k \ge 1$, half-graphs $B_k$ with $k \ge 1$ and their disjoint unions, $k$-double stars $D_k$ with $n \ge 2$, and almost complete thin sums $T_{2\ell}$ with $\ell \ge 3$.

In particular, this showed that the OSD-numbers of cliques, half-graphs and their disjoint unions attain the upper bound in Theorem 1. Moreover, we provided an equivalent reformulation of the OSD-problem as a covering problem in a suitable hypergraph composed of the closed neighborhoods and the symmetric differences of open neighborhoods of vertices. We also discussed the polyhedra associated with the OSD-codes, particularly, in relation to the OLD-codes of some graph families already studied in this context. The latter illustrated how polyhedral
arguments can be used to determine lower bounds for OSD-numbers, how an
analysis of the OSD-clutter can provide the OSD-codes, and that combining
both arguments can yield the OSD-numbers of the studied graphs.

The future lines of our research include studying the OSD-problem on more
graph families and also searching for extremal cases concerning the lower bounds
for OSD-numbers (that is, the logarithmic bound in Theorem 1 and the LD-
number in Theorem 2).

Even though the problem of deciding if the OSD- and the OLD-numbers dif-
fer is NP-complete in general, it would be interesting to see if for some particular
graph families, this problem becomes polynomial-time solvable. In that case, it
would be further interesting to provide a complete dichotomy as to for which
graphs of that graph family the two code-numbers differ and for which they
are equal. Finally, it would be interesting to address the question of whether or
not similar relations as for OSD- and OLD-numbers of a graph (who differ by at
most one) also hold for ID- and DTD-numbers (combining closed-separation with
domination and total domination, respectively) and for LD- and LTD-numbers
(combining location with domination and total domination, respectively) on con-
nected graphs (e.g. by bounding their possible differences).

**Acknowledgments.** This research was financed by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-0016), by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and the International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25.

References

1. Argiroffo, G., Bianchi, S. : On the set covering polyhedron of circulant matrices, Discrete Optimization **6**, 162-173 (2009).

2. Argiroffo, G., Bianchi, S., Lucarini, Y., Wagler, A. K.: Polyhedra associated with identifying codes in graphs, Discrete Applied Mathematics **245**, 16–27 (2018).

3. Argiroffo, G., Bianchi, S., Lucarini, Y., Wagler, A. K.: Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs. Discrete Applied Mathematics **322**, 465-480 (2022).

4. Babai, L.: On the complexity of canonical labeling of strongly regular graphs, SIAM Journal on Computing, **9**(1), 212–216 (1980).

5. Balas, E., Ng, S. M.: On the set covering polytope: I. All the facets with coefficients in {0,1,2}, Mathematical Programming **43**, 57–69 (1989).

6. Bondy, J. A.: Induced Subsets. Journal of Combinatorial Theory **12**(B), 201-202 (1972).

7. Charon, I., Hudry, O., Lobstein, A., Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoretical Computer Science **290**, 2109–2120 (2003).

8. Colburn, C., Slater, P.J., Stewart, L.K., Locating-dominating sets in series-parallel networks, Congressus Numerantium **56**, 135–162 (1987).
arguments can be used to determine lower bounds for OSD-numbers, how an
analysis of the OSD-clutter can provide the OSD-codes, and that combining
both arguments can yield the OSD-numbers of the studied graphs.

The future lines of our research include studying the OSD-problem on more
graph families and also searching for extremal cases concerning the lower bounds
for OSD-numbers (that is, the logarithmic bound in Theorem 1 and the LD-
number in Theorem 2).

Even though the problem of deciding if the OSD- and the OLD-numbers dif-
fer is NP-complete in general, it would be interesting to see if for some particular
graph families, this problem becomes polynomial-time solvable. In that case, it
would be further interesting to provide a complete dichotomy as to for which
graphs of that graph family the two code-numbers differ and for which they
are equal. Finally, it would be interesting to address the question of whether or
not similar relations as for OSD- and OLD-numbers of a graph (who differ by at
most one) also hold for ID- and DTD-numbers (combining closed-separation with
domination and total domination, respectively) and for LD- and LTD-numbers
(combining location with domination and total domination, respectively) on con-
nected graphs (e.g. by bounding their possible differences).

**Acknowledgments.** This research was financed by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-0016), by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25) and the International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25.

References

1. Argiroffo, G., Bianchi, S. : On the set covering polyhedron of circulant matrices, Discrete Optimization **6**, 162-173 (2009).

2. Argiroffo, G., Bianchi, S., Lucarini, Y., Wagler, A. K.: Polyhedra associated with identifying codes in graphs, Discrete Applied Mathematics **245**, 16–27 (2018).

3. Argiroffo, G., Bianchi, S., Lucarini, Y., Wagler, A. K.: Polyhedra associated with locating-dominating, open locating-dominating and locating total-dominating sets in graphs. Discrete Applied Mathematics **322**, 465-480 (2022).

4. Babai, L.: On the complexity of canonical labeling of strongly regular graphs, SIAM Journal on Computing, **9**(1), 212–216 (1980).

5. Balas, E., Ng, S. M.: On the set covering polytope: I. All the facets with coefficients in {0,1,2}, Mathematical Programming **43**, 57–69 (1989).

6. Bondy, J. A.: Induced Subsets. Journal of Combinatorial Theory **12**(B), 201-202 (1972).

7. Charon, I., Hudry, O., Lobstein, A., Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoretical Computer Science **290**, 2109–2120 (2003).

8. Colburn, C., Slater, P.J., Stewart, L.K., Locating-dominating sets in series-parallel networks, Congressus Numerantium **56**, 135–162 (1987).
9. Cornuéjols, G., Combinatorial Optimization: Packing and Covering, SIAM, CBMS 74 (2001).

10. Foucaud, F., Ghareghani, N., Roshani-Tabrizi, A., Sharifani, P.: Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics 302, 76-79 (2021).

11. Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE transactions on information theory 44(2), 599-611 (1998).

12. Haynes, T.W., Henning, M. A., Howard, J.: Locating and total-dominating sets in trees, Discrete Applied Mathematics 154, 1293-1300 (2006).

13. Jean, J., Lobstein, A.: Watching systems, identifying, locating-dominating and discriminating codes in graphs, https://dragazo.github.io/bibdom/main.pdf

14. Nobili, P., Sassano, A., Facets and lifting procedures for the set covering polytope, Mathematical Programming 45, 111-137 (1989).

15. Pikhurko O., Veith H., and Verbitsky O.: The first order definability of graphs: Upper bounds for quantifier depth, Discrete Applied Mathematics, 154(17), 2511-2529 (2006).

16. Slater, P.J.: Dominating and reference sets in a graph, Journal of Mathematical and Physical Sciences 22, 445-455 (1988).

17. Seo, S.J., Slater, P.J.: Open neighborhood locating dominating sets, Australasian Journal of Combinatorics 46, 109-119 (2010).

18. Ungrangsi, R., Trachtenberg, A. and Starobinski, D.: An Implementation of Indoor Location Detection Systems Based on Identifying Codes, "Intelligence in Communication Systems", Springer Berlin Heidelberg", 175-189 (2004).
9. Cornuéjols, G., Combinatorial Optimization: Packing and Covering, SIAM, CBMS 74 (2001).

10. Foucaud, F., Ghareghani, N., Roshani-Tabrizi, A., Sharifani, P.: Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics 302, 76-79 (2021).

11. Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE transactions on information theory 44(2), 599-611 (1998).

12. Haynes, T.W., Henning, M. A., Howard, J.: Locating and total-dominating sets in trees, Discrete Applied Mathematics 154, 1293-1300 (2006).

13. Jean, J., Lobstein, A.: Watching systems, identifying, locating-dominating and discriminating codes in graphs, https://dragazo.github.io/bibdom/main.pdf

14. Nobili, P., Sassano, A., Facets and lifting procedures for the set covering polytope, Mathematical Programming 45, 111-137 (1989).

15. Pikhurko O., Veith H., and Verbitsky O.: The first order definability of graphs: Upper bounds for quantifier depth, Discrete Applied Mathematics, 154(17), 2511-2529 (2006).

16. Slater, P.J.: Dominating and reference sets in a graph, Journal of Mathematical and Physical Sciences 22, 445-455 (1988).

17. Seo, S.J., Slater, P.J.: Open neighborhood locating dominating sets, Australasian Journal of Combinatorics 46, 109-119 (2010).

18. Ungrangsi, R., Trachtenberg, A. and Starobinski, D.: An Implementation of Indoor Location Detection Systems Based on Identifying Codes, "Intelligence in Communication Systems", Springer Berlin Heidelberg", 175-189 (2004).