A set $S$ of vertices of a digraph $D$ is called an open neighbourhood locating dominating set if every vertex in $D$ has an in-neighbour in $S$, and for every pair $u,v$ of vertices of $D$, there is a vertex in $S$ that is an in-neighbour of exactly one of $u$ and $v$. The smallest size of an open neighbourhood locating-dominating set of a digraph $D$ is denoted by $\gamma_{OL}(D)$. We study the class of digraphs $D$ whose only open neighbourhood locating dominating set consists of the whole set of vertices, in other words, $\gamma_{OL}(D)$ is equal to the order of $D$, which we call extremal. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. Extending some previous studies from the literature for both open neighbourhood locating-dominating sets and identifying codes of both undirected and directed graphs (which all correspond to studying special classes of digraphs), we prove general structural properties of such extremal digraphs, and we describe how they can all be constructed. We then use these properties to give new proofs of several known results from the literature. We also give a recursive and constructive characterization of the extremal digraphs whose underlying undirected graph is a tree.

§ INTRODUCTION

We consider extremal questions regarding the open neighbourhood location-domination problem on directed graphs (digraphs for short). This problem is part of the area of identification problems in discrete structures (such as graphs, digraphs or hypergraphs). In this type of problems, one wishes to uniquely determine some elements of the structure (usually the vertices or the edges) by means of a solution set (of vertices, edges or substructures), in the sense that each element to be distinguished is covered by a unique subset of the solution. This type of problems has been studied under various names and in different contexts such as separating systems, discriminating codes, or test collections, see for example [3, 4, 6, 21, 25, 28]. They have many applications to various domains such as biological testing [25], threat detection in facilities [34] or fault diagnosis in computer networks [23, 27].

The concept of open neighbourhood location-dominating sets (OLD sets for short) was defined for undirected graphs under the name of IDNT codes by Honkala, Laihonen and Ranto in <cit.> and independently re-discovered by Seo and Slater in [30, 31], who coined the term “OLD set”. We extend the definition to digraphs in a natural way, as the definition of dominating sets for undirected graphs is classically extended to digraphs. Given a digraph $D$, a set $S$ of vertices is an open neighbourhood location-dominating set of $D$ if (i) every vertex has an in-neighbour in $S$ (open neighbourhood domination condition) and (ii) for every pair of vertices, there is a vertex on $S$ that is an in-neighbour of exactly one of the two vertices (open neighbourhood location condition). The open neighbourhood location-domination number (OLD number for short) of $D$, denoted $\gamma_{OL}(D)$, is the smallest size of an OLD set of $D$. Note that a digraph with a vertex of in-degree 0 or with two vertices with the same in-neighbourhood (called in-twins), does not admit any OLD set, but if the graph does not contain any such vertices, the whole vertex set is an OLD set. A digraph is called locatable if it admits an OLD set.

Since their introduction over a decade ago, OLD sets have been extensively studied, see [10, 15, 16, 19, 21, 24, 26, 31] for some papers on the topic. OLD sets are related to locating-dominating sets, defined by Slater in the 1980s [32, 33], where the open neighbourhood domination condition is replaced by closed neighbourhood domination, and the location condition is only required for pairs of vertices that are not in the solution set. In the related notion of identifying codes, one replaces open (in-)neighbourhoods in both conditions by closed (in-)neighbourhoods. These notions were mainly studied for undirected graphs, but locating-dominating sets of digraphs were studied in [1, 5, 9, 14, 29] and identifying codes of digraphs were studied
in [2, 8, 9, 11, 17, 29].

In this paper, our goal is to study those digraphs whose only OLD set is the whole set of vertices.

Previous results. All undirected graphs whose only OLD set is the whole set of vertices were characterized in [13], as the family of half-graphs defined in [12] (a half-graph is a special bipartite graph with both parts of the same size, where each part can be ordered so that the open neighbourhoods of consecutive vertices differ by exactly one vertex). Digraphs with no directed 2-cycles whose only identifying code is the whole set of vertices were characterized in [17], as transitive closures of top-down oriented forests. The aim of this paper is to study the set of digraphs whose only OLD set is the whole set of vertices. In fact, the above results can be reformulated in our setting.

A digraph is called reflexive if each vertex has a loop. When a vertex has a loop, then its open in-neighbourhood is the same as its closed in-neighbourhood. Thus, for a reflexive digraph, the concept of an OLD set is the same as the one of an identifying code, as defined above. A digraph is symmetric if for each arc $xy$, the arc $yx$ also exists. A symmetric digraph can be seen as an undirected graph. Thus, considering OLD sets of digraphs where loops are allowed, generalizes previous works on identifying codes of both digraphs and undirected graphs, and on OLD sets of undirected graphs.

The underlying (undirected) graph of a digraph is the one obtained by transforming each arc into an edge (and removing multiple edges). A rooted directed tree is a directed graph without loops and directed 2-cycles whose underlying graph is a tree, which contains a single source called root, and where each arc is oriented away from the root. Using this terminology, we can reformulate existing results from the literature in our setting as follows (the two first theorems were proved in the context of identifying codes).

For a connected, symmetric, reflexive and locatable digraph $D$ of order $n$, $\gamma_{OL}(D)=n$ if and only if $n=1$.

For a connected reflexive locatable digraph $D$ of order $n$ without directed 2-cycles, $\gamma_{OL}(D)=n$ if and only if the digraph obtained from $D$ by removing all loops is the transitive closure of a rooted directed tree.

For a connected symmetric and loop-free locatable digraph $D$ of order $n$, $\gamma_{OL}(D)=n$ if and only if the underlying graph of $D$ is a half-graph.

Also note that both OLD sets and identifying codes can be seen as a special case of discriminating codes in bipartite graphs, studied in [6, 7]. Given a bipartite graph $G$ with partite sets $I$ and $A$, a discriminating code of $G$ is a subset $C$ of vertices of $A$ such that each vertex of $I$ has a unique and nonempty neighbourhood within $C$. Given a digraph $D$, one can construct a bipartite graph where $I$ and $A$ are two copies of $V(D)$ and a vertex in $I$ is adjacent to all vertices in $A$ corresponding to its in-neighbours in $D$. Now, a subset $C$ of $A$ is a discriminating code in the bipartite graph if and only if it is an OLD set in $D$. A similar construction (with closed in-neighbourhoods instead of open in-neighbourhoods) can be done for identifying codes [17]. The problem of studying those bipartite graphs where all vertices of $A$ are required in any discriminating code was one of the main problems studied in [6], and thus the present paper partially answers this question.

Our results. We first study, in Section <ref>, general properties of digraphs of order $n$ with OLD number $n$. In such digraphs, every vertex is needed in every OLD set (forced), either to dominate a vertex, or to locate a pair of vertices. We show that however, in such a digraph, no vertex can be double-forced (i.e. forced because of two distinct reasons). We also show that the vertex set of such graphs can always be partitioned into subsets, each of which contains a spanning directed cycle.
We then give a characterization of the (very rich) class of digraphs of order $n$ with OLD number $n$. We use the found structural properties and the characterization to give new proofs of Theorem <ref>, Theorem <ref> and Theorem <ref> in Section <ref>. Then, we focus, in Section <ref>, on the class of extremal digraphs whose underlying graph is a tree, and give a recursive and constructive characterization of these digraphs. We conclude in Section <ref>.

Definitions. In this paper, we consider directed graphs (digraphs for short) which can contain loops. A digraph with no loops and with at most one arc between any pair of vertices is called an oriented graph. An arc from vertex $x$ to vertex $y$ is denoted $xy$, its tail is $x$ and its head is $y$. Multiple arcs between the same pair of vertices are allowed, but two arcs with the same tail and head are meaningless, so we assume they do not occur. The in-neighbourhood of a vertex $x$ of $D$ is denoted by $N_D^-(v)$, and similarly $N_D^+(v)$ is the out-neighbourhood of $v$ (we may drop the $D$ subscripts if $D$ is clear from the context). By the underlying graph of a digraph $D$, we mean the undirected simple graph (without loops and repeated edges) on vertex set $V(D)$ obtained from $D$ by adding an edge between $x$ and $y$ if there exists an arc in $D$ between $x$ and $y$. A directed cycle is a sequence of arcs such that the head of each arc is the same as the tail of the next one, the head of the last arc is the same as the tail of the first arc, and every vertex occurs only in two arcs of the sequence.

§ STRUCTURAL PROPERTIES OF DIGRAPHS $D$ OF ORDER $N$ WITH $\GAMMA_{OL}(D)=N$

We now describe the structure of digraphs whose only OLD set is the whole vertex set. There are many such graphs, as we will see. To achieve this, we will first prove some preliminary results.

§.§ Forced vertices

In a locatable digraph $D$, some vertices have to belong to any OLD set: we call such vertices forced, as was done in e.g. [18] in the context of identifying codes. There are two types of forced vertices: those that are forced because of the domination condition, and those that are forced because of the location condition.

Let $D$ be a locatable digraph. A vertex $v$ of $D$ is called domination-forced if there exists a vertex $w$, such that $v$ is the unique in-neighbour of $w$. Vertex $v$ is called location-forced if there exist two distinct vertices $x$ and $y$, such that $N^-(x)\ominus N^-(y)=\{v\}$ (where $\ominus$ denotes the set symmetric difference). A vertex $v$ is called double-forced, if either it is both domination-forced and location-forced, or it is location-forced because of two different pairs of vertices.

We can observe the following.

If there is a vertex $v$ in a locatable digraph $D$ which is neither domination-forced nor location-forced, then $V(D)\setminus\{v\}$ is an OLD set of $D$.

Since $v$ is not domination-forced, every vertex of $D$ has an in-neighbour in $V(D)\setminus\{v\}$. Moreover since $v$ is not location-forced, for every pair $z,w$ of distinct vertices in $D$, there is a vertex in $V(D)\setminus\{v\}$ in the symmetric difference $N^-(z)\ominus N^-(w)$, which therefore distinguishes $z$ and $w$.

Proposition <ref> implies that in any locatable digraph $D$ of order $n$ with $\gamma_{OL}(D)=n$, every vertex is domination-forced or location-forced (or both). (In fact we will show in Proposition <ref> that if  $\gamma_{OL}(D)=n$, no vertex could be both domination-forced and location-forced.)

We get a direct corollary of Proposition <ref>, which will be used several times in the proofs of Section <ref>.

Let $D$ be a digraph of order $n$ with $\gamma_{OL}(D)=n$. If a vertex is not domination-forced (resp. location-forced), then it must be location-forced (resp. domination-forced).

Before proving our characterization, we will use the following celebrated theorem of Bondy, which is important for our line of work (see for example [17] and references therein).

Let $V$ be an $n$-set, and $\mathcal{A}=\{\mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_n\}$ be a family of $n$ distinct subsets of $V$. There is a $(n-1)$-subset $X$ of $V$ such that the sets $\mathcal{A}_1\cap X, \mathcal{A}_2\cap X, \mathcal{A}_3\cap X,\ldots, \mathcal{A}_n\cap X$ are still distinct.

Every locatable digraph $D$ of order $n$ has at most $n-1$ location-forced vertices.

Construct from digraph $D$ the set system with $V(D)$ as its $n$-set and where the $A_i$'s are all the open in-neighbourhoods of vertices of $D$. Theorem <ref> implies that there is one vertex such that removing it does not create two same open in-neighbourhoods. In other words, this vertex is not location-forced.

§.§ Forcing arcs

We next define special arcs that are remarkable when it comes to forced vertices.

Let $D=(V,A)$ be a directed graph of order $n$ with $\gamma_{OL}(D)=n$. Then the arc $xy\in A$ is called a forcing arc if either $N^-(y)=\{x\}$ or there is a vertex $z\in V$ such that $N^-(y)\setminus N^-(z) =\{x\}$. A forcing cycle is a cycle all whose arcs are forcing arcs.

Note that a vertex is forced if and only if it is the tail of a forcing arc. Thus, if $D$ has only forced vertices, every vertex has a forcing outgoing arc.

The next lemma is important for our study.

Let $D$ be a digraph of order $n$ with $\gamma_{OL}(D)=n$. Let $x$ be an arbitrary vertex of $D$ and let $D'$ be the digraph obtained from $D$ by deleting all non-forcing arcs of $D$, which have $x$ as their tails. Then, $D'$ is locatable and $\gamma_{OL}(D')=n$. Moreover, if $x$ is not location-forced, then $D$ and $D'$ have the same sets of forcing arcs.

First, we prove that $D'$ is locatable. Towards a contradiction, suppose that there exist two in-twins: vertices $y$ and $z$ such that $N_{D'}^-(y)=N_{D'}^-(z)$. Since $D$ is locatable, we conclude that $x$ had exactly one of $y$ and $z$ as an out-neighbour in $D$; without loss of generality suppose that $xy$ is an arc of $D$. But then, $xy$ would be a forcing arc and it would not have been deleted from $D$, a contradiction. Moreover, assume that there is a vertex $t$ of in-degree 0 in $D'$. Then, $x$ must have been the only in-neighbour of $t$ in $D$, but then the arc $xt$ would be forcing and $t$ would have in-degree 1 in $D'$, a contradiction. Therefore, $D'$ is locatable.

We will now show that every vertex of $D'$ is the tail of a forcing arc, implying that $\gamma_{OL}(D')=n$, and that if $x$ is not location-forced, then $D$ and $D'$ have the same sets of forcing arcs.

By Proposition <ref>, all vertices of $D$ are either domination-forced or location-forced. By deleting all non-forcing arcs of $D$ which have $x$ as their tail, it is clear that all domination-forced vertices remain domination-forced, and each forcing arc $xy$ having a domination-forced vertex as its tail remains forcing.

Next, consider a location-forced vertex $t$ in $D$, that is, there are two vertices $u$ and $v$ such that $N_D^-(u)\setminus N_D^-(v)=\{t\}$; thus, $tu$ is a forcing arc in $D$. If $x$ is not an in-neighbour of $u$ and $v$, or if $x=t$, then we still have $N_{D'}^-(u)\setminus N_{D'}^-(v)=\{t\}$ and $tu$ is still a forcing arc in $D'$: we let $\varphi(tu)=tu$. Otherwise, $x$ is an in-neighbour of both $u$ and $v$ in $D$ (possibly, $x=u$ or $x=v$). If both arcs $xu$ and $xv$ are non-red or both are forcing, then again $N_{D'}^-(u)\setminus N_{D'}^-(v)=\{t\}$ and $tu$ is still a forcing arc in $D'$. If $xu$ is forcing and $xv$ is non-red in $D$, since $u$ has both $x$ and $t$ as in-neighbours, $xu$ is a location-forcing arc and there is a vertex $w$ with $N^-(u)\setminus N^-(w)=\{x\}$. But then, in $D'$, we have $N^-(w)\setminus N^-(v)=\{t\}$. Thus, $t$ is still location-forced in $D'$. Though the forcing arc $tu$ is no longer forcing in $D'$, now the arc $tw$ is forcing in $D'$ (and in that case we had that $x$ is location-forced).

Assume next that $xv$ is forcing and $xu$ is non-red in $D$. If $xv$ is forcing because of domination, it means that $x$ is the unique in-neighbour of $v$ in $D$, and thus $u$ is dominated only by $x$ and $t$; in $D'$, $u$ is dominated only by $t$, and thus in $D'$ the arc $tu$ remains forcing and $t$ is now domination-forced. Otherwise, $xv$ is forcing because of location: there is a vertex $w$ such that $N_{D}^-(v)\setminus N_{D}^-(w)=\{x\}$. Then, notice that in $D'$, we have $N_{D'}(u)\setminus N_{D'}(w)=\{t\}$. Thus, the arc $tu$ stays forcing in $D'$ and $t$ is still location-forced.

This means that each vertex of $D'$ is either domination-forced or location-forced, and thus, we conclude that $\gamma_{OL}(D')=n$. Moreover, the only case where $D'$ and $D$ had different sets of forcing arcs occurred when $x$ was location-forced, as claimed.

We next show that in a digraph $D$ of order $n$ and $\gamma_{OL}(D)=n$, no two forcing arcs can have the same tail.

Any digraph $D$ of order $n$ with $\gamma_{OL}(D)=n$ contains no double-forced vertex.

We prove this by induction on $n$. We can assume $D$ is connected, as it suffices to prove the claim for each connected component. If $n=1$, the only locatable digraph has a single vertex with a loop, for which the claim is clearly true. If $n=2$, one can check that there are three connected locatable digraphs of order 2 and in fact they all have OLD number 2 (see Figure <ref>). For each of them the claim is true.

Let $n\geq 3$ and assume the result is true for all digraphs $D$ of order $m<n$ with $\gamma_{OL}(D)=m$.
Towards a contradiction, suppose that there is a digraph $D$ of order $n$ with $\gamma_{OL}(D)=n$, which contains a double-forced vertex.
Among all such digraphs of order $n$, let $D=(V, A)$ be a digraph which has the smallest number of arcs.

Let $z\in V$ be a double-forced vertex of $D$. By Corollary <ref>, there is a vertex $x$ in $D$ which is not location-forced, hence it is domination-forced. So, there is a vertex $y\in V$ with $N^-(y)=\{x\}$ and $xy$ is a forcing arc (possibly $x=y$ and the arc is a loop).
Since $x$ is not location-forced, and there cannot be another vertex that has $x$ as its unique in-neighbour (otherwise it would be an in-twin of $y$), we conclude that $xy$ is the unique forcing arc which has $x$ as its tail.

Now, we claim that $N^+(x)=\{y\}$. Indeed, otherwise, we can delete all non-forcing arcs from $D$ which have  $x$ as their tails, to obtain a new digraph $D'$; by Lemma <ref>, $\gamma_{OL}(D')=n$ and the set of forcing arcs of $D$ and $D'$ are the same. Thus, all double-forced vertices of $D$ remain double-forced in $D'$, in particular, there is at least such a vertex in $D'$. This is a contradiction to the minimality of $D$ in terms of the number of its arcs. Therefore, we have $N^+(x)=\{y\}$ as claimed. As $n\geq 3$ and $D$ is connected, this implies that $x\neq y$.

Now, let $D''$ be the digraph obtained from $D$ by contracting the arc $xy$ and let $v_{xy}$ be the new vertex representing both $x$ and $y$. Then, every domination-forced vertex of $D$ (except $x$) remains domination-forced in $D''$. Moreover, every location-forced vertex of $D$ remains location-forced in $D''$ (note that $v_{xy}$ is domination-forced in $D''$ if $y$ was domination-forced in $D$, and is location-forced if $y$ was location-forced in $D$). Hence, $\gamma_{OL}(D'')=n-1$ and the vertex $z$ (or $v_{xy}$ if $z=y$) is double-forced in $D''$, which contradicts the induction hypothesis. Thus, $D$ does not exist, a contradiction which completes the proof.

[small node](x00) at (-2,0)    ;
[thick,densely dashed,-Latex[scale=1.1]] (x00) edge[out=50,in=110,loop, min distance=10mm] node  (x00);

[small node](x1) at (0,0)    ;
[small node](y1) at (2,0)    ;
[small node](x2) at (4,0)    ;
[small node](y2) at (6,0)    ;
[small node](x3) at (8,0)    ;
[small node](y3) at (10,0)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x1) edge[out=40,in=140,min distance=5mm] node  (y1);
[thick,densely dashed,-Latex[scale=1.1]] (y1) edge[out=220,in=320,min distance=5mm] node  (x1);
[thick,densely dashed,-Latex[scale=1.1]] (x2) edge[out=40,in=140,min distance=5mm] node  (y2);
[thick,densely dashed,-Latex[scale=1.1]] (y2) edge[out=220,in=320,min distance=5mm] node  (x2);
[thick,-Latex[scale=1.1]] (x2) edge[out=150,in=210,loop, min distance=10mm] node  (x2);
[thick,-Latex[scale=1.1]] (x3) edge node  (y3);
[thick,densely dashed,-Latex[scale=1.1]] (x3) edge[out=150,in=210,loop, min distance=10mm] node  (x3);
[thick,densely dashed,-Latex[scale=1.1]] (y3) edge[out=330,in=30,loop, min distance=10mm] node  (y3);

The four connected locatable digraphs of order 1 and 2. Forcing arcs are dashed.

§.§ Structural properties of extremal digraphs

Let $D$ be a digraph of order $n$ and $D'$ be the subgraph of $D$ induced by the forcing arcs of $D$. Then, $\gamma_{OL}(D)=n$ if and only if $D'$ is the disjoint union of directed cycles that spans the whole vertex set of $D$.

Assume $\gamma_{OL}(D)=n$. By repeated use of Lemma <ref>, we deduce that $D'$ is locatable and $\gamma_{OL}(D')=n$. Thus, each vertex of $D'$ is forced, has at least one in-neighbour, and at least one out-neighbor. In fact, by Proposition <ref>, each vertex of $D'$ has exactly one out-neighbour. Thus, there is a total of $n$ arcs in $D'$, and so, every vertex of $D'$ has exactly one in-neighbour and one out-neighbour, and $D'$ is the disjoint union of directed cycles.

Conversely, if $D'$ is the disjoint union of directed cycles, then $\gamma_{OL}(D')=n$. By Lemma <ref>, $D$ and $D'$ have the same set of forced vertices, thus $\gamma_{OL}(D)=n$.

By Theorem <ref>, every vertex $v$ of a digraph $D$ of order $n$ with $\gamma_{OL}(D)=n$ has a unique outgoing and a unique incoming forcing arc (possibly they are the same if $v$ has a forcing loop). We will denote by $f^-(v)$ and $f^+(v)$ the unique in-neighbour and out-neighbour of $v$, respectively, given by these forcing arcs (if $v$ has a forcing loop, we have $f^+(v)=f^-(v)=v$).

Theorem <ref> implies that in a digraph $D$ of order $n$ with $\gamma_{OL}(D)=n$, every vertex appears in a directed cycle, thus we get the following corollary.

Let $D$ be a digraph of order $n$ containing a source or a sink. Then, $\gamma_{OL}(D)\leq n-1$.

We also get the following corollary.

If each vertex of a digraph $D$ is forced, then $D$ is locatable.

By Theorem <ref>, every vertex of $D$ has an in-neighbour. Assume by contradiction that $D$ contains two vertices $x$ and $y$ with the same in-neighborhood. By Theorem <ref>, $x$ has a forcing incoming arc, $tx$. Thus, there is an arc $ty$ but by Proposition <ref> $ty$ is not forcing. Hence, $t$ is not the only in-neighbour of $y$, and $x,y$ have at least two in-neighbours. Thus, $t$ is location-forced and there is a vertex $z$ with $N^-(x)\setminus N^-(z)=\{t\}$. But this implies $N^-(y)\setminus N^-(z)=\{t\}$ and the arc $ty$ should be forcing, contradicting Proposition <ref>.

Given a digraph $D$, we define the digraph $\mathcal{H}(D)$ on vertex set $V(D)$, where $x$ has an arc to $y$ if and only if there exists a vertex $v$ of $D$ that is location-forced, with $N^-(x)=N^-(y)\setminus\{v\}$ (possibly, $v=y$, in which case $y$ has a forcing loop; if $v=x$, then $x$ has no loop but there is a forcing arc from $x$ to $y$ in $D$).

Such a construction was previously defined in [18] in the context of identifying codes. We will now give some properties of $\mathcal{H}(D)$ when $D$ is an extremal digraph.

Let $D$ be a locatable digraph of order $n$ with $\gamma_{OL}(D)=n$. Then,
$\mathcal{H}(D)$ is the disjoint union of rooted directed trees, where for each root $r$, $f^-(r)$ is domination-forced in $D$ (and thus $r$ has only one in-neighbour in $D$), and for each other vertex $v$, $f^-(v)$ is location-forced in $D$ (and thus, $v$ has an in-neighbour in $\mathcal{H}(D)$).

Since an arc $xy$ in $\mathcal{H}(D)$ implies that the in-neighbourhood of $x$ is strictly smaller than that of $y$, it is clear that $\mathcal{H}(D)$ is acyclic. Moreover, if some vertex $x$ has two in-neighbours $y,z$ in $\mathcal{H}(D)$, then we would have that $N^-(y)=N^-(x)\setminus\{f^-(x)\}=N^-(z)$, contradicting the fact that $D$ is locatable. Thus, $\mathcal{H}(D)$ is acyclic and each vertex has at most one in-neighbour, hence $\mathcal{H}(D)$ is the disjoint union of rooted directed trees.

By the definition of $\mathcal{H}(D)$, each vertex $v$ with an in-neighbour in $\mathcal{H}(D)$ has an incoming forcing arc $wv$ where $w=f^-(v)$ is location-forced. This completes the proof.

Using Theorem <ref> and Theorem <ref>, one can show how all extremal digraphs can be built, as follows.

For any locatable digraph $D$ of order $n$, we have $\gamma_{OL}(D)=n$ if and only if $D$ can be constructed as follows.

* First, choose a decomposition of $n$ as a sum of positive integers $n_1,\ldots n_k$, corresponding to the orders of the directed cycles $C_1,\ldots,C_k$ consisting of all forced arcs of $D$.

* Next, choose a partition of $V(D)$ into a set $V_d$ of domination-forced vertices and a set $V_l$ of location-forced vertices.

* Then, construct $\mathcal{H}(D)$ as a set of vertex-disjoint rooted directed trees (note that such a tree may consist of a single vertex), as follows. The roots of the trees are precisely the out-neighbours of the vertices in $V_d$. Moreover, for any vertex $x$ of $V_l$, its out-neighbour $f^+(x)$ has an in-neighbour in $\mathcal{H}(D)$.

* Finally, for each rooted directed tree $T$ of $\mathcal{H}(D)$ and every vertex $v$ of $T$, we create an arc from $f^-(v)$ to all descendants of $v$ in $T$.

Assume that $\gamma_{OL}(D)=n$, it follows from Theorem <ref> and Theorem <ref> that $D$ must be constructed in the above way.

Conversely, if $D$ is constructed in this way, the digraph is locatable and each vertex is forced, and thus it satisfies $\gamma_{OL}(D)=n$.

An example of the construction of Theorem <ref> is depicted in Figure <ref>.

node distance = 2cm,

every state=[draw = black, thick, fill = white,minimum size = 1mm]
[shape=rectangle,draw=black] (1) at (0,2.5) 1;
[shape=circle,draw=black] (3) at (0,0) 3;
[shape=circle,draw=black] (2) at (2.5,2.5) 2;
[shape=circle,draw=black] (0) at (2.5,0) 4;

at (1.25,-1) (a) The forcing arcs of $D$;

[draw,very thick, dashed, color=black](2) edge node[left]  (1);
[draw,very thick, dashed, color=black](1) edge node[left]  (3);
[draw,very thick, dashed, color=black](3) edge node[left]  (2);
[draw,very thick,dashed] (0) edge[out=50,in=100,loop, min distance=10mm] node  (0);

[shape=rectangle,draw=black] (4) at (6,2.5) 1;
[shape=circle,draw=black] (6) at (6,0) 3;
[shape=circle,draw=black] (5) at (8.5,2.5) 2;
[shape=circle,draw=black] (7) at (8.5,0) 4;

at (7.25,-1) (b) The rooted directed tree $\mathcal{H}(D)$;
decoration=snake,amplitude=.3mm,segment length=2mm,
post length=0.4mm,pre length=0.5mm
[decorate] (5) – (4);
[decorate] (6) – (5);
[decorate] (6) – (7);

[shape=rectangle,draw=black] (8) at (12,2.5) 1;
[shape=circle,draw=black] (9) at (12,0) 3;
[shape=circle,draw=black] (10) at (14.5,2.5) 2;
[shape=circle,draw=black] (11) at (14.5,0) 4;

at (13.25,-1) (c) The final digraph $D$;

[draw,very thick, dashed, color=black](10) edge node[left]  (8);
[draw,very thick, dashed, color=black](8) edge node[left]  (9);
[draw,very thick, dashed, color=black](9) edge node[left]  (10);

[draw,thick] (8) edge[bend left] (10);
[draw, color=black](8) edge node[bend left]  (11);
[draw,thick] (9) edge[bend left] (8);
[draw,thick] (8) edge[out=50,in=100,loop, min distance=10mm] node  (8);
[draw,very thick,dashed] (11) edge[out=50,in=100,loop, min distance=10mm] node  (11);

An example of the construction from Theorem <ref>. The square vertex is the only one in $V_d$; the circled vertices are those in $V_l$; the dashed arcs are the forcing arcs; the wriggled arcs are those of $\mathcal H(D)$.

§ NEW PROOFS OF KNOWN RESULTS

In this section, we show that the previously discussed results enable us to give new proofs of already known results.

§.§ A new proof of Theorem <ref>

We note that Corollary <ref>, which is directly derived from Theorem <ref> by Bondy [4], in fact implies Theorem <ref> (this gives a different proof than the one from [20]).

Let $D$ be a connected, reflexive, symmetric and locatable digraph of order $n$. If $\gamma_{OL}(D)=n$, by Proposition <ref>, every vertex of $D$ is either location-forced or domination-forced. By Corollary <ref>, $D$ has at most $n-1$ location-forced vertices, and so, it has at least one domination-forced vertex. However, since $D$ is reflexive and symmetric, a domination-forced vertex of $D$ is necessarily a vertex with no neighbours other than itself. Since $D$ is connected, we must have $n=1$.

§.§ A new proof of Theorem <ref>

Our tools can be used to give a new proof of Theorem <ref> from [17] (the original proof was using induction) which states that a reflexive digraph of order $n$ with no directed 2-cycles satisfies $\gamma_{OL}(D)=n$ if and only if $D$ is obtained from the transitive closure of a rooted directed tree by adding a loop to each vertex.

It is not difficult to see that if $D$ is obtained from the transitive closure of a rooted directed tree by adding a loop to each vertex, then $\gamma_{OL}(D)=n$ as the root of the tree is domination-forced, and each vertex is location-forced to locate itself from its parent in the tree.

For the other direction, let $D$ be a connected reflexive locatable digraph of order $n$ with no directed 2-cycle, and assume that $\gamma_{OL}(D)=n$.

First of all, we claim that the forcing arcs in $D$ are exactly its loops. Assume by contradiction that it is not the case, and there is a forcing arc from $x$ to $y$ with $x\neq y$. Then, there is a vertex $z$ such that $N^-(y)\setminus N^-(z)=\{x\}$ (thus, $z\notin\{x,y\}$ since $x$ is an in-neighbour of both $x$ and $y$ since there is a loop at $x$). Since there is a loop at both $y$ and $z$, there is an arc from $y$ to $z$ and vice-versa, contradicting the fact that there is no directed 2-cycle in $D$. Thus, each forcing arc is a loop, and by Theorem <ref>, the set of forcing arcs of $D$ is exactly its set of loops.

Now, consider the digraph $\mathcal{H}(D)$ from Definition <ref>. By Theorem <ref>, it consists of a disjoint union of rooted directed trees. Since every vertex is dominated by itself through its loop, every domination-forced vertex is the root of one of the directed trees of $\mathcal{H}(D)$. Consider a location-forced vertex $x$ of $D$, and assume its in-neighbour in $\mathcal{H}(D)$ is $y$. By the previous paragraph we have $f^-(x)=x$ and thus, since $y$ has a loop, we must have the arc $yx$ in $D$ as well. Thus, $\mathcal{H}(D)$ is in fact a subdigraph of $D$. Moreover, for any two vertices $x,y$ in the same rooted directed tree of $\mathcal{H}(D)$, where $x$ is a descendant of $y$, we have the arc $yx$ in $D$.

Moreover, we claim that there is a unique tree in $\mathcal{H}(D)$. For a contradiction, suppose there are at least two of them (each of which has a domination-forced vertex as its root). Recall that $\mathcal{H}(D)$ is a subdigraph of $D$. Since $D$ is connected, there must be two trees $T_1$ and $T_2$ with an arc say, from a vertex $x_1$ of $T_1$ to a vertex $x_2$ of $T_2$. But then, $x_1$ must be an in-neighbour of all vertices of $T_2$, and thus the root of $T_2$ is in fact not domination-forced, a contradiction.

This shows that $D$ is obtained from the transitive closure of a rooted directed tree by adding a loop to each vertex, as claimed.

§.§ A new proof of Theorem <ref>

We next give a new proof using our structural theorems, that for every connected locatable symmetric and loop-free digraph of order $n$ with $\gamma_{OL}(D)=n$, the underlying graph of $D$ is a half-graph. We recall the definition of a half-graph: for any integer $k\geq 1$, the half-graph $H_k$ is the undirected bipartite graph on vertex sets $\{v_1,\ldots,v_k\}$ and $\{w_1,\ldots,w_k\}$, with an edge between $v_i$ and $w_j$ if and only if $i\leq j$.

Assume that $D$ is a connected, locatable, loop-free and symmetric digraph of order $n$ with $\gamma_{OL}(D)=n$.
By Theorem <ref>, we know that the set of forcing arcs of $D$ induces a disjoint union of directed cycles.

First we show that all these directed cycles are, in fact, 2-cycles. Towards a contradiction, assume this is not the case, and let $C$ be a directed cycle of forcing arcs of length other than 2. Since $D$ is loop-free, there are no forcing loops, and so, $C$ has length at least 3. Let $c_1,c_2,\ldots,c_k$ be the vertices of $C$, ordered along the natural orientation of $C$. Since $D$ is symmetric, each vertex of $C$ has at least two in-neighbours, thus no vertex of $C$ is domination-forced, and they are all location-forced. Thus, for each vertex $c_i$ of $C$, there is a vertex $c'_i$ such that $N^-(c_i)\setminus\{c_{i-1}\}=N^-(c'_i)$. Consider $i=2$. Since $D$ is symmetric, we have $c_{3}$ which has an arc to $c_2$, and thus, there are symmetric arcs between $c_{3}$ and $c'_2$ as well. Thus, since $N^-(c_{3})\setminus\{c_{2}\}=N^-(c'_{3})$, there must also exist symmetric arcs between $c'_2$ and $c'_{3}$. However, since $N^-(c_2)\setminus\{c_{1}\}=N^-(c'_2)$ and $c_{1}\neq c_{3}$, there must be symmetric arcs between $c_2$ and $c'_{3}$. But this contradicts the fact that $N^-(c_{3})\setminus\{c_{2}\}=N^-(c'_{3})$, and proves the claim.

By Corollary <ref>, we know that $D$ contains at least one domination-forced vertex. Let $v_1$ be a domination-forced vertex of $D$ and $u_1=f^-(v_1)$. Since every forced-cycle of $D$ is of length $2$, we conclude that $v_1=f^-(u_1)$. Now, $d^-(u_1)=1$, since $v_1$ is domination-forced. Since $D$ is symmetric, We have $d^+(u_1)=1$. If $u_1$ is also domination-forced, since $D$ is connected, then $D$ is of order $2$ and its underlying graph is the half-graph of order 2. Otherwise, there is a vertex $v_2$ such that $N^-(v_1)\setminus N^-(v_2)=\{u_1\}$.

Now, if $u_2$ is domination-forced, then $v_1$ and $v_2$ have no additional neighbours. Thus, the only neighbour of $v_2$ is $u_2$, which has at least two in-neighbours, and thus, $v_2$ cannot be domination-forced. Thus, $v_2$ is location-forced, and since $f^-(u_2)=v_2$, there is a vertex $u_3$ such that $N^-(u_2)\setminus N^-(u_3)=\{v_2\}$. Thus, $u_3$ must have $v_1$ as an in-neighbour, and in fact we have $u_1=u_3$ and there are no other vertices in $D$. Now, we are done since the underlying graph of $D$ is a half-graph of order 4.

Otherwise, $u_2$ is location-forced, and since $f^-(v_2)=u_2$, there is a vertex $v_3$ such that $N^-(v_2)\setminus N^-(v_3)=\{u_2\}$. We can continue this procedure until we reach a domination-forced vertex $u_k$. Then the procedure stops, and the underlying graph of $D$ is a half-graph of order $2k$, which completes the proof.

§ A RECURSIVE AND CONSTRUCTIVE CHARACTERIZATION OF EXTREMAL DIGRAPHS WHOSE UNDERLYING GRAPH IS A TREE

In this section, we characterize digraphs whose underlying graph is a tree. We are going to give a recursive construction for all of these digraphs. We start with the following definitions.

For a positive integer, $n$, we define $\mathcal{T}_n$ as the set of all (connected) digraphs $D$ of order $n$ with $\gamma_{OL}(D)=n$, whose underlying graph is a tree.

For an undirected graph $G$, we say that an induced path with vertices $u_0, u_1, \ldots , u_n$ of $G$ is called
a pendant path of length $n$ of $G$, if
$deg(u_1)= \ldots = deg(u_{n-1})=2$ and $deg(u_n)=1$
(note there is no requirement on the degree of $u_0$).

Let $D\in \mathcal{T}_n$ and $T$ be the underlying tree of $D$. Then, For each vertex $v$ of $D$, $d^-(v)\leq 2$.

Let $v$ be a vertex of $D$ with $d^-(v)>1$, then $f^-(v)$ is not domination-forced, so it is location-forced. It means that there is a vertex $u\in V(D)$ such that $N^-(v)=N^-(u)\cup \{f^-(v)\}$. If $d^-(v)\geq 3$, we conclude that vertices $v$ and $u$ have at least two common in-neighbors, so the underlying graph $T$ contains a cycle of length more than two, which is a contradiction. Hence  $d^-(v)\leq 2$, as desired.

Recall that by Theorem <ref>, the forcing arcs of an extremal digraph $D$ induce a disjoint union of directed cycles that spans the entire vertex set of $D$. If the underlying graph of $D$ is a tree, then these cycles are either loops or directed 2-cycles. In particular, if a vertex is loop-free, it is incident with a directed 2-cycle.

Let $D\in \mathcal{T}_n$ and $T$ be the underlying tree of $D$. Then for each location-forced vertex $v$ of $D$, $d^+(v)=1$.

Let $v$ be a location-forced vertex of $D$. For contrary suppose that there exits a vertex $x\neq f^-(v)$ such that $vx \in A(D)$. By Lemma <ref>, we have $N^-(x)=\{f^-(x),v\}$.
Hence, $f^-(x)$ is not domination-forced and so it is location-forced. Therefore, there exists a vertex $y$ such that $N^-(x)\setminus N^-(y)=\{f^-(x)\}$. We conclude that $N^-(y)=\{v\}$, this means that $v$ is domination-forced which contradicts Proposition <ref>.

We next prove two structural lemmas.

Let $D\in \mathcal{T}_n$ and $T$ be the underlying tree of $D$.
Suppose that $a$ is a leaf in $T$ with a forcing loop attached to $a$. Then, there is no cycle of length 2 in $D$ which contains $a$.

Towards a contradiction, suppose that there is a cycle of length 2 containing the arcs $ab$ and $ba$ (by Theorem<ref>, we know that none of these two arcs are forcing arcs). Since $d^-(a)=2$, we conclude that $f^-(a)=a$ is not domination-forced, and hence by Proposition <ref>, it is location-forced.
Hence, there exists a vertex $c$ such that $N^-(a)\setminus N^-(c)=\{a\}$, which means that $N^-(c)=\{b\}$. (Note that $b\neq c$.) Therefore, $b$ is domination-forced, and since all forcing cycles are of length at most 2, we conclude that $bc$ and $cb$ are both forcing arcs. Since $d^-(b)\geq 2 $ (in fact by Lemma <ref>, $d^-(b)= 2$), $c$ cannot be domination-forced, and by Proposition <ref>, it is location-forced.
Since $cb$ is a forcing arc, we conclude that there is a vertex $f$ such that $N^-(b)\setminus N^-(f)=\{c\}$, which means that $N^-(f)=\{a\}$. The latter means that $af$ is also a forcing arc and $a$ is domination-forced and so it is double-forced, which contradicts Theorem <ref>. Thus, the proof is complete.

Let $D\in \mathcal{T}_n$ and $T$ be the underlying tree of $D$. Then, either $D$ contains a forcing loop at a leaf $a$ of $T$, or $T$ contains a pendant path of length 2 whose leaf is contained in a forcing $2$-cycle.

We recall that by Theorem <ref>, every leaf belongs to a unique forcing cycle in $D$ (of length at most 2). If $T$ contains a pendant path of length 2 whose leaf is contained in a forcing cycle of length 2 in $D$ or is contained in a forcing loop, then we are done. Otherwise, $T$ should not have any pendant path of length 2. But then, $T$ contains two leaves adjacent to the same vertex. At least one of these two leaves must have a forcing loop attached, which concludes the proof.

§.§ The case of a leaf with a forcing loop attached

Next, we give a recursive construction for digraphs
$D\in \mathcal{T}_n$, which contain a forcing loop on a leaf. To this aim, we will use digraphs $D'\in \mathcal{T}_{n-1}$.

Let $n>2$ be an integer, $D\in \mathcal{T}_n$ and $T$ be the underlying graph of $D$. Suppose that $a$ is a leaf in $T$ with a forcing loop attached and $b$ is the unique neighbour of $a$ in $T$.
Letting $D'=D\setminus \{a\}$, then $D'\in \mathcal{T}_{n-1}$. Moreover, if $ba\in A(D)$, then $b$ is domination-forced in $D$ and also in $D'$. If
$ab\in A(D)$, then $f^-_{D'}(b)$ is domination-forced in $D'$, $d^+_{D}(f_D^-(b))=1$ and $b$ has no loop attached.

By Proposition <ref>, $a$ is either location-forced or domination-forced in $D$. First suppose that $a$ is location-forced. Using Lemmas <ref> and <ref>, we conclude that $N^-(a)=\{a,b\}$ and $ab\not \in A(D)$.  As $a$ is location-forced, there is a vertex $x$ such that $N_D^-(x)=N_D^-(a)\setminus \{a\}=\{b\}$ and hence $b=f^-(x)$, or equivalently $b$ is domination-forced (in both $D$ and $D'$). Since all cycles of $D$ have length at most 2, we have $x=f^-(b)$. Now, we note that by deleting the vertex $a$ and its adjacent arcs, the set of in-neighbours of any remaining vertex does not change. Hence, all domination-forced (resp. location-forced) vertices of $D$ remain domination-forced (resp. location-forced) in $D'$, and so $D'\in \mathcal{T}_{n-1}$, as claimed.

Now, suppose that $a$ is domination-forced, which implies that $ba\not \in A(D)$, so $ab\in A(D)$ and $N^-(a)=\{a\}$. By Theorem <ref>, $f_D^-(b)\neq a$. Hence, $x=f_D^-(b)$ (possibly, $x=b$) is location-forced in $D$. By Lemma <ref>, we have $d^-_D(b)=2$, hence $d^-_{D'}(b)=1$ and so, $f_{D'}^-(b)$ is domination-forced in $D'$.

Now, we are going to prove that $d^+(f^-_{D}(b))=1$. By contradiction, suppose that $d^+(x)>1$. Then, there exists a vertex $y\neq b$ such that $xy\in A(D)$. since $y\neq b$, $f^-(y)\neq x$. By Lemma <ref>, $N^-(y)=\{x, f^-(y)\}$, we deduce that $f^-(y)$ is not domination-forced, and so it is location-forced. Hence, there is a vertex $z\in V(D)$ such that $N^-(y)\setminus N^-(z)=\{f^-(y)\}$. This implies that $N^-(z)=\{x\}$, and thus $x$ is domination-forced. But as we proved above, $x$ is location-forced and so it is double-forced, which contradicts Proposition <ref>. Thus, $d^+_D(x)=1$, as claimed.

Next, we show that there is no loop at $b$ in $D$. Otherwise, since by Lemma <ref>, $d^-_D(b)\leq 2$, $f_D^-(b)=b$, and so as mentioned before, $b$ is location-forced in $D$. Since $D$ is connected and has more than two vertices, we conclude that there is a vertex $c\neq b$ in $D'$ such that $bc\in A(D)$.
Since $f_D^-(c)\neq b$, we have $d^-_D(c)=2$, and so $f_D^-(c)$ is not domination-forced. Thus, by Proposition <ref>, it is location-forced in $D$. Therefore, there is a vertex $d$ in $D$ such that $N^-_D(c)\setminus N^-_D(d)=\{f_D^-(c)\}$, and thus, $N^-_D(d)=\{b\}$. This implies that $b$ is domination-forced and thus it is double-forced, contradicting Proposition <ref>. Therefore, $f_D^-(b)\neq b$ and we conclude that there is no loop at $b$ in $D$, as claimed.

To complete the proof of the lemma, we must show that if $a$ is domination-forced, $D'\in \mathcal{T}_{n-1}$. By deleting the vertex $a$ and its incident arcs, for every vertex $v\neq b$ of $D'$, we have $N^-_{D'}(v)=N^-_D(v)$. On the other hand, by Lemma <ref>, $d^-_D(b)=2$ and so, $d^-_{D'}(b)=1$, which shows that $x=f_D^-(b)$ is domination-forced in $D'$. Hence, all domination-forced (resp. location-forced) vertices of $V(D)\setminus \{x\}$ remain domination-forced (resp. location-forced) in $D'$, and $x$ is domination-forced. Therefore, all vertices are forced and $D'\in \mathcal{T}_{n-1}$, as desired.

We now show the converse of Lemma <ref>.

Let $n>1$ be an integer and $D'$ be a digraph in $\mathcal{T}_{n-1}$, and $b\in V(D')$. Suppose that $D$ is a digraph with $V(D)=V(D')\cup\{a\}$ and the arc set of $D$ is defined using one of the following rules.

i.  If $b$ is domination-forced in $D'$, then $A(D)=A(D')\cup \{ba, aa\}$.

ii. If $bb\not\in A(D)$, $d^+_{D'}(f^-(b))=1$ and
$f^-_{D'}(b)$ is domination-forced in $D'$,  then
$A(D)=A(D')\cup \{ab, aa\}$.

Then, $D\in \mathcal{T}_n$.

Since $b$ is domination-forced, $N_D^-(a)\setminus N_D^-(f^-(b))=\{a\}$, therefore, $a$ is location-forced in $D$. On the other hand, if a vertex is domination-forced (resp. location-forced) in $D'$, then it is
domination-forced (resp. location-forced) in $D$. Hence, $D\in \mathcal{T}_n$, as desired.

ii. In this case, since  $N_D^-(a)=\{a\}$, we conclude that $a$ is domination-forced. Since $N_D^-(b)\setminus N_D^-(a)=\{f_{D'}^-(b)\}$, $f^-_{D'}(b)$ is location-forced in $D$. Moreover, it is easy to see that all domination-forced vertices of $D'$ except $f^-_{D'}(b)$, remain domination-forced in $D$, and since  $d^+_{D'}(f^-(b))=1$, all location-forced vertices in $D'$ remain location-forced in $D$. Hence, $D\in \mathcal{T}_n$.

§.§ The case of a pendant path of length 2 whose leaf is contained in a forcing 2-cycle

In the following lemma, we give a recursive construction for digraphs
$D\in \mathcal{T}_n$ with underlying tree $T$,
in which $T$ contains a pendant path of length 2 whose leaf is contained in a forcing $2$-cycle. In this recursive construction, we will use digraphs $D'\in \mathcal{T}_{n-2}$.

Let $n\geq 3$ be an integer, $D\in \mathcal{T}_n$ and $T$ be the underlying tree of $D$. Let $P=c b a$ be a pendant path of length 2 in $T$. Assume that $d_T(a)=1$, $D'=D\setminus \{a,b\}$ and vertices $a,b$ are contained in a common forcing $2$-cycle. Then, $D'\in\mathcal{T}_{n-2}$. Moreover, the  following conditions hold:

i. $aa\not \in A(D)$;

ii. If $bb\in A(D)$, then $cb\not\in A(D)$. Moreover, $f^-(c)$ is location-forced in $D$ and domination-forced in $D'$. Moreover, if $c=	f^-(c)$, then the only possibility for $D$ is  the digraph shown in Figure <ref>(a).

iii. If $bb\not \in A(D)$ and $f^-(c)$ is domination-forced in $D$, then $N^-_D(c)=\{f^-(c)\}$ and $f^-(c)\neq b$. Hence, $bc \not \in A(D)$ and since $D$ is connected, $cb\in A(D)$.

iv. If $bb\not \in A(D)$ and $c$ is domination-forced in $D$ and $f^-(c)$ is location-forced, then $d^+_D(f^-(c))=1$.

v. If $bb\not \in A(D)$ and $c$ and $f^-(c)$ are both location-forced in $D$, then $cb\not\in A(D)$ and $bc\in A(D)$. Moreover, if $c=f^-(c)$, then the only possibility for $D$ is the digraph shown in Figure <ref>(b).

node distance = 2cm,

every state=[
draw = black,
fill = white,
minimum size = 1mm

[shape=circle,draw=black] (1) at (0,0) $a$;
[shape=circle,draw=black] (2) at (2.5,0) $b$;
[shape=circle,draw=black] (3) at (5,0) $c$;

[draw,very thick,dashed] (1) edge[bend left] (2);
[draw,very thick,dashed] (2) edge[bend left] (1);
[draw,very thick, color=black](2) edge node[left]  (3);
[draw,very thick,dashed] (3) edge[out=50,in=100,loop, min distance=10mm] node  (3);
[draw,very thick] (2) edge[out=50,in=100,loop, min distance=10mm] node  (2);
(title) at (2.5,-3/2) (a) ;

[shape=circle,draw=black] (1) at (8,0) $a$;
[shape=circle,draw=black] (2) at (10.5,0) $b$;
[shape=circle,draw=black] (3) at (13,0) $c$;

[draw,very thick,dashed] (1) edge[bend left] (2);
[draw,very thick,dashed] (2) edge[bend left] (1);
[draw,very thick, color=black](2) edge node[left]  (3);
[draw,very thick,dashed] (3) edge[out=50,in=100,loop, min distance=10mm] node  (3);
(title) at (10.5,-3/2) (b) ;

Two extremal connected locatable digraphs of order 3. Forcing arcs are dashed.

In the following, we prove that $D$ satisfies the claimed conditions.

i. For a contradiction, suppose that $aa\in A(D)$. By Lemma <ref>, we conclude that $d^-(a)=2$, and thus $b=f^-(a)$ is location-forced; then there is a vertex $x$ such that $N^-(a)\setminus N^-(x)=\{b\}$, which shows that $N^-(x)=\{a\}$. Since $a$ is a leaf in $T$, we conclude that $x=b$ and $cb\not \in A(D)$. Since $b$ is location-forced, by Lemma <ref>, $d^+_D(b)=1$ and $bc \not \in A(D)$. Since the underlying graph of $D$ is connected we conclude that $a$ and $b$ are the only vertices of $D$, which contradicts the assumption that $n\geq 3$.

ii. Since $ab\in A(D)$, using Lemma <ref>, we conclude that $cb\not\in A(D)$ and so $bc\in A(D)$. Since $b\neq f^-(c)$, by Lemma <ref>, $d^-(c)=2$. Therefore, we conclude that $f^-(c)$ is location-forced in $D$ (and domination-forced in $D'$) and by Lemma <ref>, $d^+_D(f^-(c))=1$.

Moreover, if $c=f^-(c)$, then $d^+_D(c)=1$ and by Lemma <ref>, $N^-_D(c)=\{c,b\}$. Hence, the vertex $c$ does not have any in-neighbour, other than $b$ and $c$ nor any out-neighbour, other than $c$, in $D$. Therefore, the only possibility for $D$ is the digraph shown in Figure <ref>(a).

iii.  Suppose $bb\not \in A(D)$ and $f^-(c)$ is domination-forced in $D$. Then, $N^-_D(c)=\{f^-(c)\}$ and $f^-(c)\neq b$. Hence, $bc \not \in A(D)$.

iv. We have $d^+(f^-(c))=1$ by Lemma <ref>.

v. By contradiction, suppose that $cb\in A(D)$, then by Lemma <ref>, $N^-(b)=\{c,a\}$ and thus $a$ is not domination-forced. Since $f^-(b)=a$ and $a$ is location-forced,
there is a vertex $y$ such that $N^-(b)\setminus N^-(y)=\{a\}$. Then $N^-(y)=\{c\}$, this shows that $c$ is domination-forced. Hence, $c$ is both location-forced and domination-forced, which is a contradiction by Proposition <ref>. Thus, $cb\not\in A(D)$ and since $D$ is connected, $bc\in A(D)$.

Now suppose that $c=f^-(c)$, then by Lemma <ref>, $d^+_D(c)=1$ and by Lemma <ref>, $N^-_D(c)=\{c,b\}$. Hence the vertex $c$ does not have any in-neighbour other than $b$ and $c$ or out-neighbour other than $c$, and the only possibility for $D$ is the digraph shown in Figure <ref>(b).

We now show the converse of Lemma <ref>.

Let $D'\in \mathcal{T}_{n-2}$ and $c$ be an arbitrary vertex of $D'$. Suppose that $D$ is a digraph with $V(D)=V(D')\cup\{a,b\}$ and the arc set of $D$ is defined using one of the following rules:

i. If $c$ and $f^-(c)$ are both domination-forced in $D'$ and $d_{D'}^+(f^-(c))=1$, then $A(D)=A(D')\cup \{ ab, ba\}\cup A$, where $A\in \{\{bb, bc\}, \{cb,bc\}, \{bc\}, \{cb\}\}$.

ii. If $c$ is location-forced in $D'$, $f^-(c)$ is domination-forced in $D'$ and $d_{D'}^+(f^-(c))=1$, then $A(D)=A(D')\cup \{bb, bc, ab, ba\}$ or $A(D)=A(D')\cup \{bc, ab, ba\}$.

iii. If $c$  and $f^-(c)$ are both domination-forced in $D'$, and $d_{D'}^+(f^-(c))>1$ then $A(D)=A(D')\cup \{cb, ab, ba\}$.

iv. If $c$ is domination-forced in $D'$  and $f^-(c)$ is location-forced in $D'$,  then $A(D)=A(D')\cup \{cb, ab, ba\}$.

Then $D\in \mathcal{T}_n$.

First we note that if
$d_{D'}^+(f^-(c))=1$ (cases i and ii), then $N_{D'}^+(f^-(c))=\{c\}$. So in this case there is no vertex $y$ such that $N^-(y)\setminus N^-(c)=\{f^-(y)\}$. Hence, if the new digraph $D$ is constructed by adding some new in-neighbours to $c$, this does not affect the forcing vertices of $D'$, other than $f^-(c)$. Thus, to prove that $D$ is extremal in cases i and ii, it suffices to show that by adding the set of new arcs, each vertex from the set $\{a,b,c,f^-(c)\}$ is a forced vertex in $D$.

Moreover, as in cases iii and iv, we do not add any in-neighbours to $c$, the same applies to these cases as well.

As the vertices $c$ and $f^-(c)$ are both domination-forced in $D'$, we conclude that $N_{D'}^-(f^-(c))=\{c\}$ and $N_{D'}^-(c)=\{f^-(c)\}$. Since $d_{D'}^+(f^-(c))=1$, there is no vertex $x\neq c$ such that  $f^-(c)\in N_{D'}^-(x)$.

Therefore, if $A(D)=A(D')\cup \{bb, bc, ab, ba\}$, then $N_{D}^-(a)=\{b\}$, $N_{D}^-(b)=\{a,b\}$ and $N_{D}^-(c)=\{f^-(c),b\}$. Hence, $b$ is domination-forced in $D$, $a$ and $f^-(c)$ are both location-forced in $D$.

If $A(D)=A(D')\cup \{cb, bc, ab, ba\}$, then $N_{D}^-(a)=\{b\}$, $N_{D}^-(b)=\{a,c\}$ and $N_{D}^-(c)=\{f^-(c),b\}$. Hence, $b$ is domination-forced in $D$, $f^-(c)$ and $a$ are both location-forced in $D$ (the latter because there is a vertex in $D$ only dominated by $c$).

If $A(D)=A(D')\cup \{ bc, ab, ba\}$, $N_{D}^-(a)=\{b\}$, then $N_{D}^-(b)=\{a\}$ and $N_{D}^-(c)=\{f^-(c),b\}$. Hence, $b$ and $a$ are both domination-forced in $D$ and $f^-(c)$ is location-forced in $D$.

Finally, If $A(D)=A(D')\cup \{cb, ab, ba\}$, then $N_{D}^-(a)=\{b\}$, $N_{D}^-(b)=\{a,c\}$ and $N_{D}^-(c)=\{f^-(c)\}$. Hence, $b$ and $f^-(c)$ are both domination-forced in $D$ and $a$ is location-forced in $D$ (because there is a vertex in $D$ only dominated by $c$).

In all cases, $c$ remains domination-forced.

Moreover, assume that $v$ is a vertex of $D'$ which is different from $c$ and $f^-_{D'}(c)$. It is easy to see that if $v$ is domination-forced (resp. location-forced) in $D'$, then it would be
domination-forced (resp. location-forced) in $D$.
Therefore, we conclude that each vertex of $D$ is either domination-forced or location-forced which implies that $D\in \mathcal{T}_n$, as desired.

ii. Since $f^-(c)$ is domination-forced in $D'$, $N_{D'}^-(c)=\{f^-(c)\}$.
First suppose that $A(D)=A(D')\cup \{bb, bc, ab, ba\}$. Since $N_D^-(b)=\{a\}\cup N_D^-(a)$ and $N_D^-(a)=\{b\}$, we conclude that $a$ is location-forced and $b$ is domination-forced in $D$. Since $N_D^-(c)=\{f^-(c)\}\cup N_D^-(a)$, $f^-(c)$ is location-forced in $D$ and one can see that $c$ remains location-forced in $D$. Therefore, in this case $D\in \mathcal{T}_n$.

Now, suppose that $A(D)=A(D')\cup \{bc, ab, ba\}$. Since $N_D^-(b)=\{a\}$ and $N_D^-(a)=\{b\}$, we have that $a$ and $b$ are both domination-forced in $D$. On the other hand,  $N_D^-(c)=\{f^-(c)\}\cup N_D^-(a)$, so $f^-(c)$ is location-forced in $D$ and again one can see that $c$ remains location-forced in $D$.
Hence, $D\in \mathcal{T}_n$.

iii. Since $c$ and $f^-(c)$ are both domination-forced in $D'$, we have $N_{D'}^-(f^-(c))=\{c\}$ and $N_{D'}^-(c)=\{f^-(c)\}$. Considering  $N_{D}^-(a)=\{b\}$, $N_{D}^-(b)=\{a,c\}$, $N_{D}^-(f^-(c))=\{c\}$ and $N_{D}^-(c)=\{f^-(c)\}$, it is easy to see that $b$, $c$ and $f^-(c)$ are all domination-forced in $D$ and $a$ is location-forced. Hence, $D\in \mathcal{T}_n$ $D\in \mathcal{T}_n$ as desired.

It is easy to see that $b$ and $c$ are domination-forced  and $f^-(c)$ remains location-forced in $D$. Since $c$ is domination-forced in $D'$, $N_{D}^-(f^-(c))=N_{D'}^-(f^-(c))=\{c\}$, hence $N_{D}^-(b)=\{a\}\cup N_{D}^-(f^-(c))$ and $a$ is location-forced in $D$. Therefore, $D\in \mathcal{T}_n$.

§.§ The characterization

As a conclusion of this section, we give our characterization theorem which shows how digraphs in $\mathcal{T}_n$ can be constructed recursively, using extremal digraphs of smaller order.

Let $\mathcal{C}^1(\mathcal{T}_n)$ be the set of all digraphs $D\in \mathcal{T}_{n+1}$ which are constructed from a digraph $D'\in \mathcal{T}_n$ using one of the rules given in Lemma <ref>, and $\mathcal{C}^2(\mathcal{T}_n)$ be the set of all digraphs $D\in \mathcal{T}_{n+2}$ which are constructed from a digraph $D'\in \mathcal{T}_{n}$ using one of the rules given in Lemma <ref>.

Let $n$ be a positive integer. If $n\leq 2$, then all extremal digraphs of $\mathcal{T}_{1}\cup \mathcal{T}_{2}$ are shown in Figure <ref>. If $n>2$, then, we have $\mathcal{T}_n=\mathcal{C}^1(\mathcal{T}_{n-1})\cup \mathcal{C}^2(\mathcal{T}_{n-2})$.

For $n\leq 2$, all connected locatable digraphs of these orders are those of Figure <ref> and they are all extremal. Thus, assume next that $n>2$.

By Lemma <ref>, we have $\mathcal{C}^1(\mathcal{T}_{n-1})\subseteq \mathcal{T}_n$ and by Lemma <ref>, we have $\mathcal{C}^2(\mathcal{T}_{n-2})\subseteq \mathcal{T}_n$.

Conversely, to see that $\mathcal{T}_n\subseteq\mathcal{C}^1(\mathcal{T}_{n-1})\cup \mathcal{C}^2(\mathcal{T}_{n-2})$, assume that we have a digraph $D$ in $\mathcal{T}_n$ whose underlying tree is $T$. By Lemma <ref>, either $D$ contains a forcing loop at a leaf of $T$, or $T$ contains a pendant path of length 2 whose leaf is contained in a forcing 2-cycle in $D$. In the former case, Lemma <ref> shows that $D$ can be constructed from a digraph of $\mathcal{T}_{n-1}$ by one of the rules in Lemma <ref> and thus $D\in \mathcal{C}^1(\mathcal{T}_{n-1})$. In the latter case, Lemma <ref> shows that $D$ can be constructed from a digraph of $\mathcal{T}_{n-2}$ by one of the rules in Lemma <ref> and thus $D\in \mathcal{C}^2(\mathcal{T}_{n-2})$.

We depict in Figure <ref> all extremal digraphs of order at most 4, that were constructed using Theorem <ref>.

[small node](x00) at (0,5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x00) edge[out=50,in=100,loop, min distance=10mm] node  (x00);

[small node](x01) at (1.5,5)    ;
[small node](y01) at (1.5,6.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x01) edge[bend left] (y01)	(y01) edge[bend left] (x01);

[small node](x02) at (3,5)    ;
[small node](y02) at (3,6.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x02) edge[bend left] (y02)	(y02) edge[bend left] (x02);
[thick,-Latex[scale=1.1]] (x02) edge[out=30,in=330,loop, min distance=8mm] node  (x02);

[small node](x03) at (4.5,5)    ;
[small node](y03) at (4.5,6.5)    ;

[thick,-Latex[scale=1.1]] (x03) edge node  (y03);
[thick,densely dashed,-Latex[scale=1.1]] (x03) edge[out=330,in=30,loop, min distance=8mm] node  (x03);
[thick,densely dashed,-Latex[scale=1.1]] (y03) edge[out=330,in=30,loop, min distance=8mm] node  (y03);

[small node](x1) at (6,5)    ;
[small node](y1) at (6,6.5)    ;
[small node](z1) at (6,8)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x1) edge[bend left] (y1)	(y1) edge[bend left] (x1);
[thick,-Latex[scale=1.1]] (y1) edge node  (z1);
[thick,densely dashed,-Latex[scale=1.1]] (z1) edge[out=330,in=30,loop, min distance=8mm] node  (z1);

[small node](x2) at (7.5,5)    ;
[small node](y2) at (7.5,6.5)    ;
[small node](z2) at (7.5,8)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x2) edge[bend left] (y2)	(y2) edge[bend left] (x2);
[thick,-Latex[scale=1.1]] (y2) edge node  (z2);
[thick,-Latex[scale=1.1]] (y2) edge[out=330,in=30,loop, min distance=8mm] node  (y2);
[thick,densely dashed,-Latex[scale=1.1]] (z2) edge[out=330,in=30,loop, min distance=8mm] node  (z2);

[small node](x3) at (9,5)    ;
[small node](y3) at (9,6.5)    ;
[small node](z3) at (9,8)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x3) edge[bend left] (y3)	(y3) edge[bend left] (x3);
[thick,-Latex[scale=1.1]] (z3) edge node  (y3);
[thick,densely dashed,-Latex[scale=1.1]] (z3) edge[out=330,in=30,loop, min distance=8mm] node  (z3);

[small node](x4) at (10.5,5)    ;
[small node](y4) at (10.5,6.5)    ;
[small node](z4) at (10.5,8)    ;

[thick,densely dashed,-Latex[scale=1.1]] (x4) edge[out=330,in=30,loop, min distance=8mm] node  (x4);
[thick,-Latex[scale=1.1]] (y4) edge node  (x4);
[thick,densely dashed,-Latex[scale=1.1]] (y4) edge[out=330,in=30,loop, min distance=8mm] node  (y4);
[thick,-Latex[scale=1.1]] (y4) edge node  (z4);
[thick,densely dashed,-Latex[scale=1.1]] (z4) edge[out=330,in=30,loop, min distance=8mm] node  (z4);

[small node](a01) at (0,4)    ;
[small node](b01) at (0,2.5)    ;
[small node](c01) at (0,1)    ;
[small node](d01) at (0,-0.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (a01) edge[bend left] (b01)	(b01) edge[bend left] (a01);
[thick,-Latex[scale=1.1]] (b01) edge node  (c01);
[thick,densely dashed,-Latex[scale=1.1]] (c01) edge[bend left] (d01)	(d01) edge[bend left] (c01);

[small node](a02) at (1.6,4)    ;
[small node](b02) at (1.6,2.5)    ;
[small node](c02) at (1.6,1)    ;
[small node](d02) at (1.6,-0.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (a02) edge[bend left] (b02)	(b02) edge[bend left] (a02);
[-Latex[scale=1.1]] (b02) edge[bend left]  (c02)  (c02) edge[bend left]  (b02);
[thick,densely dashed,-Latex[scale=1.1]] (c02) edge[bend left] (d02)	(d02) edge[bend left] (c02);

[small node](a03) at (3.2,4)    ;
[small node](b03) at (3.2,2.5)    ;
[small node](c03) at (3.2,1)    ;
[small node](d03) at (3.2,-0.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (a03) edge[bend left] (b03)	(b03) edge[bend left] (a03);
[thick,-Latex[scale=1.1]] (b03) edge[out=30,in=330,loop, min distance=8mm] node  (b03);
[thick,-Latex[scale=1.1]] (b03) edge node  (c03);
[thick,densely dashed,-Latex[scale=1.1]] (c03) edge[bend left] (d03)	(d03) edge[bend left] (c03);

[small node](a04) at (5,4)    ;
[small node](b04) at (5,2.5)    ;
[small node](c04) at (5,1)    ;
[small node](d04) at (5,-0.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (a04) edge[bend left] (b04)	(b04) edge[bend left] (a04);
[thick,-Latex[scale=1.1]] (c04) edge node  (b04);
[thick,densely dashed,-Latex[scale=1.1]] (c04) edge[out=330,in=30,loop, min distance=8mm] node  (c04);
[thick,-Latex[scale=1.1]] (c04) edge node  (d04);
[thick,densely dashed,-Latex[scale=1.1]] (d04) edge[out=330,in=30,loop, min distance=8mm] node  (d04);

[small node](a4) at (6.8,4)    ;
[small node](b4) at (6.8,2.5)    ;
[small node](c4) at (6.8,1)    ;
[small node](d4) at (6.8,-0.5)    ;

[thick,-Latex[scale=1.1]] (b4) edge node  (a4);
[thick,densely dashed,-Latex[scale=1.1]] (b4) edge[bend left] (c4)	(c4) edge[bend left] (b4);
[thick,densely dashed,-Latex[scale=1.1]] (a4) edge[out=330,in=30,loop, min distance=8mm] node  (a4);
[thick,densely dashed,-Latex[scale=1.1]] (d4) edge[out=330,in=30,loop, min distance=8mm] node  (d4);
[thick,-Latex[scale=1.1]] (c4) edge node  (d4);

[small node](a5) at (8.7,4)    ;
[small node](b5) at (8.7,2.5)    ;
[small node](c5) at (8.7,1)    ;
[small node](d5) at (8.7,-0.5)    ;

[thick,densely dashed,-Latex[scale=1.1]] (b5) edge[bend left] (a5)	(a5) edge[bend left] (b5);
[thick,-Latex[scale=1.1]] (c5) edge node  (b5);
[thick,densely dashed,-Latex[scale=1.1]] (c5) edge[out=330,in=30,loop, min distance=8mm] node  (c5);
[thick,densely dashed,-Latex[scale=1.1]] (d5) edge[out=330,in=30,loop, min distance=8mm] node  (d5);
[thick,-Latex[scale=1.1]] (c5) edge node  (d5);

[small node](a7) at (10.5,4)    ;
[small node](b7) at (10.5,2.5)    ;
[small node](c7) at (10.5,1)    ;
[small node](d7) at (10.5,-0.5)    ;

[thick,-Latex[scale=1.1]] (a7) edge node  (b7);
[thick,densely dashed,-Latex[scale=1.1]] (a7) edge[out=330,in=30,loop, min distance=8mm] node  (a7);
[thick,densely dashed,-Latex[scale=1.1]] (b7) edge[bend left] (c7)	(c7) edge[bend left] (b7);
[thick,densely dashed,-Latex[scale=1.1]] (d7) edge[out=330,in=30,loop, min distance=8mm] node  (d7);
[thick,-Latex[scale=1.1]] (d7) edge node  (c7);

[small node](a1) at (0,-1.5)    ;
[small node](b1) at (0,-3)    ;
[small node](c1) at (0,-4.5)    ;
[small node](d1) at (1.5,-3)    ;

[thick,densely dashed,-Latex[scale=1.1]] (b1) edge[bend left] (a1)	(a1) edge[bend left] (b1);
[thick,densely dashed,-Latex[scale=1.1]] (c1) edge[out=330,in=30,loop, min distance=8mm] node  (c1);
[thick,-Latex[scale=1.1]] (b1) edge node  (c1);
[thick,densely dashed,-Latex[scale=1.1]] (d1) edge[out=330,in=30,loop, min distance=8mm] node  (d1);
[thick,-Latex[scale=1.1]] (b1) edge node  (d1);

[small node](a2) at (3.5,-1.5)    ;
[small node](b2) at (3.5,-3)    ;
[small node](c2) at (3.5,-4.5)    ;
[small node](d2) at (5,-3)    ;

[thick,densely dashed,-Latex[scale=1.1]] (b2) edge[bend left] (a2)	(a2) edge[bend left] (b2);
[thick,densely dashed,-Latex[scale=1.1]] (c2) edge[out=330,in=30,loop, min distance=8mm] node  (c2);
[thick,-Latex[scale=1.1]] (b2) edge[out=-20,in=-70,loop, min distance=8mm] node  (b2);
[thick,-Latex[scale=1.1]] (b2) edge node  (c2);
[thick,densely dashed,-Latex[scale=1.1]] (d2) edge[out=330,in=30,loop, min distance=8mm] node  (d2);
[thick,-Latex[scale=1.1]] (b2) edge node  (d2);

[small node](a3) at (6.5,-1.5)    ;
[small node](b3) at (6.5,-3)    ;
[small node](c3) at (6.5,-4.5)    ;
[small node](d3) at (8,-3)    ;

[thick,densely dashed,-Latex[scale=1.1]] (b3) edge[bend left] (a3)	(a3) edge[bend left] (b3);
[thick,densely dashed,-Latex[scale=1.1]] (c3) edge[out=330,in=30,loop, min distance=8mm] node  (c3);
[thick,densely dashed,-Latex[scale=1.1]] (d3) edge[out=330,in=30,loop, min distance=8mm] node  (d3);
[thick,-Latex[scale=1.1]] (c3) edge node  (b3);
[thick,-Latex[scale=1.1]] (b3) edge node  (d3);

[small node](a6) at (9.5,-1.5)    ;
[small node](b6) at (9.5,-3)    ;
[small node](c6) at (9.5,-4.5)    ;
[small node](d6) at (11,-3)    ;

[thick,-Latex[scale=1.1]] (b6) edge node  (a6);
[thick,-Latex[scale=1.1]] (b6) edge node  (c6);
[thick,-Latex[scale=1.1]] (b6) edge node  (d6);
[thick,densely dashed,-Latex[scale=1.1]] (a6) edge[out=330,in=30,loop, min distance=8mm] node  (a6);
[thick,densely dashed,-Latex[scale=1.1]] (b6) edge[out=-20,in=-70,loop, min distance=8mm] node  (b6);
[thick,densely dashed,-Latex[scale=1.1]] (c6) edge[out=330,in=30,loop, min distance=8mm] node  (c6);
[thick,densely dashed,-Latex[scale=1.1]] (d6) edge[out=330,in=30,loop, min distance=8mm] node  (d6);

All extremal locatable digraphs whose underlying graph is a tree with order at most 4. Forcing arcs are dashed.

§ CONCLUSION

By studying structural properties of extremal digraphs with respect to OLD sets, we have been able to give new proofs of several existing results about both digraphs and undirected graphs, for both identifying codes and OLD sets. Indeed, OLD sets of general digraphs generalize all these problems. Thus, we believe that our results shed new light on this type of extremal problems.

We have also given a characterization of all such extremal digraphs, which, it appears, form a very rich class of digraphs. Even our recursive characterization for extremal digraphs whose underlying graph is a tree, although of course more restricted than the general case, shows that there are many such extremal trees.

[1] T. Bellitto, C. Brosse, B. Lévêque and A. Parreau. Locating dominating sets in local tournaments. Manuscript, 2021. <https://arxiv.org/abs/2109.03102>

[2] T. Y. Berger-Wolf, M. Laifenfeld and A. Trachtenberg. Identifying codes and the set cover problem. Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, Monticello, USA, September 2006.

[3] B. Bollobás and A. D. Scott. On separating systems. European Journal of Combinatorics 28:1068–1071, 2007.

[4] J. A. Bondy. Induced subsets. Journal of Combinatorial Theory, Series B 12(2):201–202, 1972.

[5] N. Bousquet, Q. Deschamps, T. Lehtilä and A. Parreau. Locating-dominating sets: from graphs to oriented graphs. Discrete Mathematics 346(1):113124, 2023.

[6] E. Charbit, I. Charon, G. Cohen, O. Hudry and A. Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Advances in Mathematics of Communications 2(4):403–420, 2008.

[7] I. Charon, G. D. Cohen, O. Hudry and A. Lobstein. Discriminating codes in (bipartite) planar graphs. European Journal of Combinatorics 29(5):1353–1364, 2008.

[8] I. Charon, S. Gravier, O. Hudry, A. Lobstein, M. Mollard and J. Moncel. A linear algorithm for minimum 1-identifying codes in oriented trees. Discrete Applied Mathematics 154(8):1246–1253, 2006.

[9] I. Charon, O. Hudry and A. Lobstein. Identifying and locating-dominating codes: NP-completeness results for directed graphs. IEEE Transactions on Information Theory 48(8):2192–2200, 2002.

[10] M. Chellali, N. Jafari Rad, S. J. Seo and P. J. Slater. On open neighbourhood locating-dominating in graphs. Electronic Journal of Graph Theory and Applications 2(2):87–98, 2014.

[11] N. Cohen and F. Havet. On the minimum size of an identifying code over all orientations of a graph. The Electronic Journal of Combinatorics 25(1):P1.49, 2018.

[12] P. Erdős. Some combinatorial, geometric and set theoretic problems in measure theory. In Measure Theory Oberwolfach 1983, pages 321–327. Springer, 1984.

[13] F. Foucaud, N. Ghareghani, A. Roshany-Tabrizi and P. Sharifani. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics 302:76–79, 2021.

[14] F. Foucaud, S. Heydarshahi and A. Parreau. Domination and location in twin-free digraphs. Discrete Applied Mathematics 284:42–52, 2020.

[15] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds. Theoretical Computer Science 668:43–58, 2017.

[16] F. Foucaud, G. B. Mertzios, R. Naserasr, A. Parreau and P. Valicov. Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity. Algorithmica 78(3):914–944, 2017.

[17] F. Foucaud, R. Naserasr and A. Parreau. Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets. Graphs and Combinatorics 29(3):463–473, 2013.

[18] F. Foucaud and G. Perarnau. Bounds on identifying codes in terms of degree parameters. The Electronic Journal of Combinatorics 19:P32, 2012.

[19] R. M. Givens, G. Yu and R. K. Kincaid. Open locating-dominating sets in circulant graphs. Discussiones Mathematicae Graph Theory 42(1):47–62, 2022.

[20] S. Gravier, and J. Moncel. On graphs having a $V\setminus\{x\}$ set as an identifying code. Discrete Mathematics 307(3-5):432–434, 2007.

[21] M. A. H. Henning and A. Yeo. Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs. Graphs and Combinatorics 30(4):909–932, 2014.

[22] I. Honkala, T. Laihonen and S. Ranto. On strongly identifying codes. Discrete Mathematics 254(1–3):191–205, 2002.

[23] M. G. Karpovsky, K. Chakrabarty and L. B. Levitin. On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory 44:599–611, 1998.

[24] R. Kincaid, A. Oldham and G. Yu. Optimal open-locating-dominating sets in infinite triangular grids. Discrete Applied Mathematics 193:139–144, 2015.

[25] B. M. E. Moret and H. D. Shapiro. On minimizing a set of tests. SIAM Journal of Scientifical and Statistical Computation 6(4):983–1003, 1985.

[26] B. S. Panda and A. Pandey. Algorithmic aspects of open neighbourhood location–domination in graphs. Discrete Applied Mathematics 216(1):290–306, 2017.

[27] N. S. V. Rao. Computational complexity issues in operative diagnostics of graph-based systems. IEEE Transactions on Computers 42(4):447–457, 1993.

[28] A. Rényi. On random generating elements of a finite Boolean algebra. Acta Scientiarum Mathematicarum Szeged 22:75–81, 1961.

[29] R. D. Skaggs. Identifying vertices in graphs and digraphs. PhD thesis, University of South Africa, South Africa, February 2007. <http://hdl.handle.net/10500/2226>

[30] S. J. Seo and P. J. Slater. Open neighbourhood locating-dominating sets. The Australasian Journal of Combinatorics 46:109–120, 2010.

[31] S. J. Seo and P. J. Slater. Open neighbourhood locating–dominating in trees. Discrete Applied Mathematics 159(6):484–489, 2011.

[32] P. J. Slater. Domination and location in acyclic graphs. Networks 17(1):55–64, 1987.

[33] P. J. Slater. Dominating and reference sets in a graph. Journal of Mathematical and Physical Sciences 22(4):445–455, 1988.

[34] R. Ungrangsi, A. Trachtenberg and D. Starobinski. An implementation of indoor location detection systems based on identifying codes. Proceedings of the IFIP International Conference on Intelligence in Communication Systems, INTELLICOMM 2004. Lecture Notes in Computer Science 3283:175–189, 2004.