hard hardness para complete completeness prb  Input: Question:

# Open-independent, open-locating-dominating sets: structural aspects of some
classes of graphs

Márcia R. Cappelle, Erika Coelho, Les R. Foulds, Humberto J. Longo

###### Abstract

Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set
$V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed
_open-dominating_ if every vertex of $G$ has at least one neighbor in $S$, and
_open-independent, open-locating-dominating_ (an $OLD_{oind}$-set for short)
if no two vertices in $G$ have the same set of neighbors in $S$, and each
vertex in $S$ is open-dominated exactly once by $S$. The problem of deciding
whether or not $G$ has an $OLD_{oind}$-set has important applications, has
been studied elsewhere and is known to be $\mathcal{NP}$-complete. Reinforcing
this result, it appears that the problem is notoriously difficult as we show
that its complexity remains the same even for just planar bipartite graphs.
Also, we present characterizations of both $P_{4}$-tidy graphs and the
complementary prisms of cographs, that have an $OLD_{oind}$-set.

1 Instituto de Informática, Universidade Federal de Goiás, Goiânia, Brazil
{marcia, erikamorais, lesfoulds<EMAIL_ADDRESS>

Keywords: open-independent, open-locating-dominating, complementary prism,
planar, bipartite, $P_{4}$-tidy, complexity.

##  1 Introduction

Consider the situation where a graph $G$ models a facility or a multiprocessor
network with limited-range detection devices (sensing for example, movement,
heat or size) placed at chosen vertices of $G$. The purpose of these devices
is to detect and precisely identify the location of an intruder such as a
thief, saboteur, vandal, fire or faulty processor that may suddenly be present
at any vertex.

As it is costly to install and maintain detection devices it is logical to
determine the locations of the minimum number of devices that can, between
them, precisely determine an intruder at any location. This challenge is often
called a _location-detection_ or an _identification_ problem and has been
well-studied [21, 25, 29]. This objective is adopted throughout the present
article. Sometimes such a device can determine if an intruder is in its
neighborhood but cannot detect if the intruder is at its own location. In this
case, it is required to find a so-called, _open-locating-dominating_ vertex
subset $S$, which is a dominating set of $G$, such that every vertex in $G$
has at least one neighbor in $S$, and no two vertices in $G$ have the same set
of neighbors in $S$. When a device may be prevented from detecting an intruder
at its own location, it is necessary to install another device in its
neighborhood. A natural way to analyze such situations is to make use of open
neighborhood sets which may have useful additional properties, such as being
open-independent, dominating, open-dominating or open-locating-dominating.
These terms and those in the next paragraph are made more precise later in
this section.

An alternative case arises when a device can determine if the intruder is
either at its own location or is in the neighborhood of its location, but
which actual location cannot be detected, and furthermore, each detector
cannot be located in the range of any other due to possible signal
interference. Such situations can potentially be analyzed via independent,
locating-dominating sets.

Finding an $OLD$-set in a given graph, if it exists, is similar to the well-
studied _identifying code problem_ [22]. An identifying code $C\subseteq V(G)$
is a dominating set where for all $u,v\in V(G)$, $u\neq v$, one has $N[u]\cap
C\neq N[v]\cap C$. The minimum cardinality of an identifying code of a graph
$G$ is denoted by $IC(G)$. Although $OLD$-sets and identifying codes are
similar notions, the parameters $OLD(G)$ and $IC(G)$ are incomparable. The
concept of an open-locating-dominating set was first considered by Seo and
Slater [31, 32]. The authors showed that to decide if a graph $G$ has such a
set is an $\mathcal{NP}$-complete decision problem and they provided some
useful results for $OLD$-sets in trees and grid graphs. Foucaud et al. [11]
presented a linear time algorithm that can be used to construct an open-
locating dominating set of minimum size for a given cograph, based on parsing
its cotree structure. Kincaid et al. [24] established the optimal density of
an OLD-set for infinite triangular grids. Savic et al. [30] presented results
on OLD-sets for some convex polytopes. We refer to [26] for an on-line
bibliography on this topic and related notions. In this paper we consider the
following more restrictive problem:

OLD-OIND (existence of an open-independent, open locating dominating set)
Instance: A graph $G$.
Question: Does $G$ have an an open-independent, open locating dominating set?

To the best of our knowledge, Seo and Slater [33] were the first to study
open-independent, open-locating-dominating sets ($OLD_{oind}$-sets for short).
They presented some results on $OLD_{oind}$-sets in paths, trees and infinite
grid graphs, and characterized $OLD_{oind}$-sets in graphs with girth at least
five. The authors also demonstrated that OLD-OIND is $\mathcal{NP}$-complete.
This complexity result was extended for complementary prisms by Cappelle et
al. [2] who presented various properties and bounds on the sizes of minimal
$OLD_{oind}$-sets in complementary prisms and showed that, if the girth of $G$
is at least four, the $OLD_{oind}$-set of its complementary prism, if it
exists, can be found in polynomial time.

In this paper we analyze the existence of $OLD_{oind}$-sets in the class of
$P_{4}$-tidy graphs and also in the complementary prism of a subclass of
$P_{4}$-tidy class, the cographs. The class of $P_{4}$-tidy graphs contains
several other graph families having relatively few $P_{4}$’s, such as the
$P_{4}$-sparse, $P_{4}$-lite, $P_{4}$-extendable and $P_{4}$-reducible graph
families. The $P_{4}$-tidy graph class generalizes all of the just-mentioned
graph families [12]. It is well known that the $P_{4}$-tidy graph class is
self-complementary and hereditary.

Haynes et al. [17] investigated several graph theoretic properties of
complementary prisms, such as independence, distance and domination. For
further study on domination parameters in complementary prisms, see [14, 7, 8,
19, 20] and for certain other parameters see [1, 6, 28, 34]. Cappelle et al.
[3] described a polynomial-time recognition algorithm for complementary
prisms. Although complementary prisms are a class of apparently well-behaved
graphs, many $\mathcal{NP}$-complete problems for general graphs remain
$\mathcal{NP}$-complete for this class. For example, independent set,
domination and $P_{3}$-convexity, as proven by Duarte et al. [9].

Our contributions. It appears that OLD-OIND is notoriously difficult as we
show that it remains $\mathcal{NP}$-complete even for just planar bipartite
graphs. However, we study some graph classes for which the problem can be
solved in polynomial time and also present characterizations of both
$P_{4}$-tidy graphs and complementary prisms of cographs that have an
$OLD_{oind}$-set.

Notation and terminology. Throughout this paper $G=(V(G),E(G))$ is assumed to
be a nontrivial, finite, simple, undirected, connected graph with vertex set
$V(G)$ and edge set $E(G)$. A subgraph of $G$ with $n$ vertices that is a path
(a cycle) is termed an $n$-path (an $n$-cycle), and is denoted by $P_{n}$
($C_{n}$). The _open neighborhood_ of a vertex $v\in V(G)$ is
$N_{G}(v)=\\{u\in V(G)\mid uv\in E(G)\\}$, and its _closed neighborhood_ is
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. Let $S\subseteq V(G)$, $S\neq\emptyset$. The
subgraph of $G$ induced by $S$ is denoted by $G[S]$. $S$ is termed
_dominating_ if every vertex not in $S$ is adjacent to at least one member of
$S$, i.e., $N_{G}[S]=\cup_{v\in S}N[v]=V(G)$. $S$ is _locating-dominating_ if
it is dominating and no two distinct vertices of $V(G)\setminus{S}$ have the
same set of neighbors in $S$, i.e., $\forall u,v\in V(G)\setminus S$, $u\neq
v$, we have that $N(u)\cap S\neq N(v)\cap S$. Clearly, $V(G)$ is a locating-
dominating set for any graph $G$. $S$ is _open-dominating_ (or _total-
dominating_) if every vertex $v\in V(G)$ has a neighbor in $S$, i.e.,
$\cup_{u\in S}N(u)=V(G)$. In this case $v$ is said to be _open-dominated_ by
$S$. $S$ is _independent_ if no two vertices in $S$ are adjacent and is _open-
independent_ (an $OIND$-set for short) if every member of $S$ is open-
dominated by $S$ at most once, i.e., $\forall\ v\in S,\ |N(v)\cap S|\leq 1$.
Obviously, an open-dominating set cannot be independent. $S$ is _open-
locating-dominating_ (an $OLD$-set for short) if it is open-dominating and no
two distinct members of $V(G)$ have the same open neighborhood in $S$, i.e.,
for all $u,v\in V(G)$, $u\neq v$, one has $N(u)\cap S\neq N(v)\cap S$. In this
case, $u$ and $v$ are said to be _distinguished_ by $S$. $G$ has an $OLD$-set
if no two of its vertices have the same open neighborhood. The minimum
cardinality of an $OLD$-set is denoted by $OLD(G)$, the open-locating-
dominating number of $G$. If $G$ has an $OLD$-set $S$, then $S$ is called an
$OLD(G)$-set if $|S|=OLD(G)$. We note that if $S$ exists, then the fact that
every leaf and its support of $G$ must be in $S$ is helpful in the proofs of
some of the theorems stated later in the present paper.

Let $G_{1}$ and $G_{2}$ be two graphs such that $V(G_{1})\cap
V(G_{2})=\emptyset$. We denote the disjoint union (resp. join) of $G_{1}$ and
$G_{2}$ by $G_{1}\oplus G_{2}$ (resp. $G_{1}\bowtie G_{2}$), and by
$\overline{G}$ the complement graph of a graph $G$. An anticomponent of a
graph $G$ is the subgraph of $G$ induced by the vertex set of a connected
component of $\overline{G}$. More precisely, an induced subgraph $H$ of $G$ is
an anticomponent if $\overline{H}$ is a connected component of $G$. Notice
that if $G_{1},G_{2},\ldots,G_{k}$ are the anticomponents of $G$, then
$G=G_{1}\bowtie G_{2}\bowtie\cdots\bowtie G_{k}$. A graph $G$ is termed co-
connected if $\overline{G}$ is connected. If $X\subseteq V(G)$, $G\setminus X$
denotes the subgraph of $G$ obtained by removing the vertices in $X$ and the
edges incident with them in $G$. For a graph $H$ and a natural number $p$,
$pH$ denotes the graph obtained by the disjoint union of $p$ copies of $H$.
For $k\geq 1$, the set $\\{1,\ldots,k\\}$ is denoted by $[k]$.

If an open-independent, open-locating-dominating set (an $OLD_{oind}$-set for
short) exists in a given graph $G$, it is often of interest to establish a set
of minimum size among such sets in $G$, which is denoted by $OLD_{oind}(G)$.
If $S$ is an $OLD_{oind}$-set for $G$, each component of $G[S]$ is isomorphic
to $K_{2}$ (the complete graph on two vertices). See, for example, the graphs
in Figures 1(a) and 1(b), where an $OLD_{oind}$-set of each graph is
represented by the black vertices.

(a) $G$.

(b) $\overline{G}$.

$V(\bar{G})$$V(G)$ (c) $G\overline{G}$.

Figure 1: Example of a graph, its complement and the resulting complementary
prism.

Haynes et al. [17] introduced the so-called complementary product of two
graphs as a generalization of the well-known Cartesian product of the graphs.
As a particular case of complementary products, the authors define the
complementary prism of a graph $G$, denoted by $G\overline{G}$, as the graph
formed from the disjoint union of $G$ and its complement $\overline{G}$ by
adding the edges of the perfect matching between the corresponding vertices of
$G$ and $\overline{G}$, where $V(G\overline{G})=V(G)\cup V(\overline{G})$. For
the purposes of illustration, a graph $G$, its complement $\overline{G}$ and
the complementary prism $G\overline{G}$ are depicted in Figure 1. To simplify
matters, $G$ and $\overline{G}$ are used to refer to the subgraph copies of
$G$ and $\overline{G}$, respectively, in $G\overline{G}$. For a set
$X\subseteq V(G)$, let $\overline{X}$ denote the corresponding vertices of $X$
in $V(\overline{G})$.

##  2 Preliminary results

Open-independent, open-locating-dominating sets were first studied by Seo and
Slater [33] who gave necessary and sufficient conditions for the existence of
an $OLD_{oind}$-set in a graph $G$ that has girth $g(G)\geq 5$. For general
graphs (with arbitrary girth), the conditions stated in Theorem 2.1 are
necessary but not sufficient, as is stated in Theorem 2.2. In our proofs we
use frequently Theorem 2.2, sometimes without mentioning the fact.

######  Theorem 2.1 ([33]).

If a graph $G$ has girth satisfying $g(G)\geq 5$ and $S\subseteq V(G)$, then
$S$ is an $OLD_{oind}$-set if and only if ($i$) each $v\in S$ is open-
dominated by $S$ exactly once and ($ii$) each $v\notin S$ is open-dominated by
$S$ at least twice.

######  Theorem 2.2 ([5]).

If $S\subseteq V(G)$ is an $OLD_{oind}$-set of a graph $G$, then ($i$) each
$v\in S$ is open-dominated exactly by $S$ once, and ($ii$) each $v\in
V(G)\setminus S$ is open-dominated by $S$ at least twice.

Seo and Slater [33] showed that OLD-OIND is an $\mathcal{NP}$-complete
problem. This result was recently extended to complementary prisms of a given
graph $G$ [2]. We use similar ideas to those in [27] for efficient edge
domination, showing that OLD-OIND is $\mathcal{NP}$-complete even for planar
bipartite graphs by polynomial reduction from the following decision problem.

X3C (exact cover by 3-sets)
Instance: A finite set $X$ with $|X|=3n$ and a collection ${\cal S}$ of
3-element subsets of $X$ with $|{\cal S}|=m$.
Question: Does ${\cal S}$ contain an exact cover of $X$ , i.e. a pairwise
disjoint subcollection ${\cal S}^{\prime}\subseteq{\cal S}$ such that every
element of $X$ occurs in exactly one member of ${\cal S}^{\prime}$?

It is well known that X3C is $\mathcal{NP}$-complete [16]. Each instance of
X3C, say $X=\\{x_{1},x_{2},\ldots,x_{3n}\\}$ and ${\cal
S}=\\{S_{1},S_{2},\ldots,S_{m}\\}$, can be associated with a bipartite graph
$G_{A}=(V_{A},E_{A})$, where $V_{A}=X\cup S$ and $E_{A}=\\{(x_{i},S_{j}):1\leq
i\leq 3n,1\leq j\leq m,x_{i}\in S_{j}\\}$. If the associated bipartite graph
$G_{A}$ is planar, the problem is termed the _planar exact cover by 3-sets
problem_ (Planar X3C). Planar X3C is also $\mathcal{NP}$-complete [10].

######  Theorem 2.3.

Deciding, for a given planar bipartite graph $G$, if $G$ has an
$OLD_{oind}$-set is an $\mathcal{NP}$-complete problem.

###### Proof.

Clearly, there is an $\mathcal{NP}$ algorithm for deciding whether or not a
planar bipartite graph has an $OLD_{oind}$-set. In the following we shall show
that Planar X3C is reducible to the problem OLD-OIND for planar bipartite
graphs in polynomial time. Let $X=\\{x_{1},x_{2},\ldots,x_{3n}\\}$ and ${\cal
S}=\\{S_{1},S_{2},\ldots,S_{m}\\}$ be an instance of Planar X3C. Then, we
construct a bipartite graph $G=(V,E)$ as follows (See Fig. 2 for an example):
$V(G)={\\{x_{i}:1\leq i\leq 3n\\}}\cup{\\{y_{ij}:1\leq i\leq 3n,1\leq j\leq
m}\mbox{ and }x_{i}\in
S_{j}\\}\cup\\{S_{j},a_{j},b_{j},c_{j},d_{j},e_{j}:1\leq j\leq m\\}$, and
$V(E)=\\{x_{i}y_{ij},y_{ij}S_{j}:1\leq i\leq 3n,1\leq j\leq m,x_{i}\in
S_{j}\\}\cup\\{S_{j}a_{j},a_{j}b_{j},b_{j}c_{j},c_{j}d_{j},d_{j}e_{j},e_{j}S_{j}:1\leq
j\leq m\\}$.

We observe that as $(X,S)$ is an instance of Planar $X3C$, $G$ is planar.
Furthermore, $V(G)$ can be partitioned into the subsets: $\\{x_{i}:1\leq i\leq
3n\\}\cup\\{S_{j},b_{j},d_{j}:1\leq j\leq m\\}$, and $\\{y_{ij}:1\leq i\leq
3n,1\leq j\leq m\mbox{ and }x_{i}\in S_{j}\\}\cup\\{a_{j},c_{j},e_{j}:1\leq
j\leq m\\}$. Hence, $G$ is bipartite. As $G$ is planar bipartite it can be
constructed in polynomial time. Now, we are going to prove that ($i$) $G$ has
an $OLD_{oind}$-set if and only if ($ii$) there is a subset ${\cal
S}^{\prime}\subseteq{\cal S}$ that is an exact cover of $X$.

To prove that ($i$) is necessary for ($ii$), assume that ${\cal S}$ has an
exact cover ${\cal S}^{\prime}$. We set
$D=\\{x_{i},y_{ij},a_{j},b_{j},d_{j},e_{j}\,:\,S_{j}\in{\cal S}^{\prime}\mbox{
and }x_{i}\in S_{j}\\}\cup\\{S_{j},a_{j},c_{j},d_{j}\,:\,S_{j}\in{\cal
S}\setminus{\cal S}^{\prime}\\}$. It is easy to verify that $D$ is an
$OLD_{oind}$-set of $G$.

To prove that ($ii$) is necessary for ($i$), assume that $G$ has an
$OLD_{oind}$-set $D$. Observe that $D$ does not contain both $S_{j}$ and
$y_{ij}$, else $a_{j},e_{j}\notin D$, which is impossible for the following
reason. Since two of the vertices in the set $\\{b_{j},c_{j},d_{j}\\}$ are in
$D$, two vertices of the 6-cycle $\langle
S_{j},a_{j},b_{j},c_{j},d_{j},e_{j}\rangle$ are dominated exactly once by $D$
and thus $D$ is not an $OLD_{oind}$-set of $G$, a contradiction. Since
$\\{S_{j},y_{ij}\\}$ is not a subset of $D$, every $x_{i}\in D$, $i\in[3n]$;
which implies that every $x_{i}$ has a neighbor $y_{ij}$ for some $j\in[m]$
such that $y_{ij}\in D$. Note that altogether, these restrictions imply that
for every $S_{j}$, the three vertices $y_{ij}$ are either all in $D$ or none
are in $D$. In the first case $S_{j}\notin D$ and
$\\{a_{j},b_{j},d_{j},e_{j}\\}\subseteq D$, otherwise $S_{j}\in D$ and one of
the two symmetric subsets $\\{a_{j},c_{j},d_{j}\\}$ and
$\\{b_{j},c_{j},e_{j}\\}$ are contained in $D$. Let ${\cal
S}^{\prime}=\\{S_{j}:1\leq j\leq m\mbox{ and }S_{j}\notin D\\}$. Clearly,
${\cal S}^{\prime}$ is an exact cover of ${\cal S}$. ∎

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$y_{11}$$y_{21}$$y_{41}$$y_{22}$$y_{42}$$y_{62}$$y_{33}$$y_{53}$$y_{63}$$S_{1}$$a_{1}$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$S_{2}$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$S_{3}$$a_{3}$$b_{3}$$c_{3}$$d_{3}$$e_{3}$
Figure 2: Graph $G$ for ${\cal
S}=\\{S_{1},S_{2},S_{3}\\}=\\{\\{x_{1},x_{2},x_{4}\\},\\{x_{2},x_{4},x_{6}\\},\\{x_{3},x_{5},x_{6}\\}\\}$.

##  3 $P_{4}$-tidy graphs

In this section, we study $OLD_{oind}$-sets in $P_{4}$-tidy graphs. A graph
$G=(V,E)$ is termed _$P_{4}$ -tidy_ if, for every vertex set $A$ inducing a
$P_{4}$ in $G$, there is at most one vertex $v\in V\setminus A$ such that
$G[A\cup\\{v\\}]$ contains at least two induced $P_{4}$’s. This class includes
spider and quasi-spider graphs, that we now define.

A _spider_ is a graph whose vertex set has a partition $(C,X,H)$, where
$C=\\{c_{1},\ldots,c_{k}\\}$ and $X=\\{x_{1},\ldots,x_{k}\\}$ for $k\geq 2$
are respectively, a clique and an independent set; $x_{i}$ is adjacent to
$c_{j}$ if and only if $i=j$ (a thin spider), or $x_{i}$ is adjacent to
$c_{j}$ if and only if $i\neq j$ (a thick spider); and every vertex of $H$ is
adjacent to each vertex of $C$ and is not adjacent to any vertex of $X$. The
size $k$, of $C$ (and $X$) is called the _weight_ of the spider and the set
$H$ in the partition is called its _head_. Notice that if $k=2$, then the
thick and thin spider graphs are isomorphic. A quasi-spider is a graph
obtained from a spider that has vertex partition $(C,X,H)$ by replacing at
most one vertex of $C\cup X$ by a $K_{2}$ or a $\overline{K_{2}}$ (where each
vertex of the $K_{2}$ or $\overline{K_{2}}$ has the same adjacencies as the
vertex they replaced).

(a) Thin spider of weight 3 and nonempty head.

(b) Thick quasi-spider of weight 3.

(c) Thin quasi-spider of weight 3.

$Z$ (d) Thick (and thin) quasi-spider of weight 2, called the $Z$ graph.

Figure 3: Examples of spider and quasi-spider graphs.

The following is a structural theorem for $P_{4}$-tidy graphs in terms of
spider and quasi-spider graphs. Spiders and quasi-spiders are co-connected
graphs.

######  Theorem 3.1 ([12]).

$G$ is a $P_{4}$-tidy graph if and only if exactly one of the following
statements holds:

  1. 1.

$G$ is the union or the join of two $P_{4}$-tidy graphs;

  2. 2.

$G$ is a spider or a quasi-spider graph with partition $(C,X,H)$ such that $H$
induces a $P_{4}$-tidy graph or is empty;

  3. 3.

$G$ is isomorphic to $C_{5}$, $P_{5}$, $\overline{P_{5}}$, or $K_{1}$.

The following two theorems settle which spiders and quasi-spiders have an
$OLD_{oind}$-set. Let the graph in Figure 3(d) be denoted by $Z$.

######  Theorem 3.2.

No spider has an $OLD_{oind}$-set.

###### Proof.

Let $G=(V(G),E(G))$ be a spider with $V(G)$ partitioned into $(C,X,H)$, where
$|C|=|X|=k\geq 2$. For a proof by contradiction suppose that $G$ has an
$OLD_{oind}$-set $S\subseteq V(G)$. We consider the subgraph $G[C\cup X]$ and
show that $S$ is either not an open-independent set, or else is not an open-
dominating set. As the cases $H\neq\emptyset$ and $H=\emptyset$ are analogous,
they are not considered further in the following proof. If $G$ is thin it
contains at least two pendant vertices, say $x_{i},x_{j}\in X$ and thus
$c_{i},c_{j}\in S$. If $x_{i}$ (resp. $x_{j}$) is not in $S$, it is dominated
once, otherwise, as $C$ is a clique, $c_{i},c_{j}$ are adjacent in $C$ and
thus, $S$ cannot be open-independent. Suppose instead that $G$ is thick. If
$k=2$, then $G$ is isomorphic to a thin spider. So, assume that $k\geq 3$. As
$C$ is a clique, $|C\cap S|\leq 2$, and the following three subcases
demonstrate that $S$ is not open-dominating.

  1. 1.

If $C\cap S=\emptyset$, each $x_{i}\in X$ must belong to $S$, but no $x_{i}$
is open-dominated by any vertex in $S$.

  2. 2.

If $|C\cap S|=1$, say $c_{i}\in S$ for a unique $i\in[k]$ then, as $G$ is
thick, $x_{i}$ is not open-dominated by $c_{i}$. Whether or not $x_{i}\in S$,
$x_{i}$ is not open-dominated by any member of $S$.

  3. 3.

If $|C\cap S|=2$, say $c_{i},c_{j}\in S$, where $i,j\in[k]$, then $x_{i}$
(resp. $x_{j}$) is not a member of $S$ and is open-dominated by only $c_{j}$
(resp. $c_{j}$). Hence, both $x_{i}$ and $x_{j}$ are open-dominated exactly
once each by $S$, and thus $S$ is not an $OLD_{oind}$-set.

∎

######  Theorem 3.3.

Any quasi-spider that has an $OLD_{oind}$-set is isomorphic to the thick and
thin quasi-spider $Z$ depicted in Fig. 3(d).

###### Proof.

Let $G=(V(G),E(G))$ be a quasi-spider obtained from a given spider $G_{s}$
that has a vertex partition $(C,X,H)$, where once again, $|C|=|X|=k\geq 2$.
Suppose $G$ is produced by applying the vertex replacement operation to a
vertex $v\in C\cup X$ in $G_{s}$ and that $G$ has an $OLD_{oind}$-set
$S\subseteq V(G)$. Again, we consider the subgraph $G[C\cup X]$ and show that
unless $k=2$, either $S$ is not an open-locating-dominating set or is not an
open-independent set of $G$ and thus cannot be an $OLD_{oind}$-set.

First we consider $k=2$. If $H=\emptyset$, since headless thick and thin
spiders of size two are isomorphic, then $G_{s}$ is a 4-path, and there are
four possibilities for $G$. In the first possibility, where either vertex in
$X$ is replaced by a $K_{2}$, $G$ is isomorphic to $Z$ and thus $G$ has an
$OLD_{oind}$-set. In the other three possibilities, where a vertex in $X$ is
replaced by a $\overline{K_{2}}$, or a vertex in $C$ is replaced by a $K_{2}$
or a $\overline{K_{2}}$; it is easy to establish by inspection that $G$ does
not have an $OLD_{oind}$-set. If $H\neq\emptyset$, then $G$ can possibly have
an $OLD_{oind}$-set only if $H$ has a dominating subset. If this is so there
are eight cases - where $G_{s}$ is either thick or thin and a vertex in either
$C$ or $X$ is replaced by either a $K_{2}$ or a $\overline{K_{2}}$. It is
straightforward to establish by inspection that none of the cases has an an
$OLD_{oind}$-set.

Now, we consider $k\geq 3$. Whether $G_{s}$ is thick or thin, there are four
cases, depending on which of the following vertex replacement operations is
applied: either $v\in C$ or $v\in X$ is replaced by either a $K_{2}$ or a
$\overline{K_{2}}$. Let $c^{\ell}_{i}$ (resp. $x^{\ell}_{i}$), $\ell=1,2$, be
the two vertices that replace vertex $v$ in $C$ (resp. $X$). When no index
$\ell$ is indicated, $c_{i}$ (resp. $x_{i}$) can be either of the two vertices
$c^{1}_{i}$ and $c^{2}_{i}$ (resp. $x^{1}_{i}$ and $x^{2}_{i}$). Replacing a
vertex in $C$ induces in $G$ either a clique or a clique with one edge
missing, denoted in either case by $\overline{C}$. As $S$ must be open-
independent to be an $OLD_{oind}$-set, it follows that $|\overline{C}\cap
S|\leq 2$. Instead, replacing a vertex in $X$ induces in $G$ either an
independent set or an independent set with one additional edge, denoted in
either case by $\overline{X}$.

If $G_{s}$ is thin, after any of the four types of replacement, the pair of
vertices in $G$ that replace $v$ cannot be distinguished and thus, in this
case, $G$ does not have an an $OLD_{oind}$-set. If $G_{s}$ is thick, similar
arguments to those used in the proof of Theorem 3.2 for thick spiders can be
applied to establish that, once again, $G$ does not have an $OLD_{oind}$-set.:

  1. 1.

If $\overline{C}\cap S=\emptyset$ then, unless a vertex $x_{i}\in X$ is
replaced by a $K_{2}$, no vertex in $X$ is open-dominated by any vertex in
$S$. If indeed, $x_{i}$ is replaced by a $K_{2}$, there are still at least two
vertices in $X$ that are not open-dominated by any vertex in $S$.

  2. 2.

If $|\overline{C}\cap S|=1$, say $c_{i}\in S$ for a unique $i\in[k]$ then, as
$G$ is thick, $x_{i}$ is not open-dominated by $c_{i}$. Whether or not
$x_{i}\in S$, $x_{i}$ is not open-dominated by any member of $S$.

  3. 3.

If $|\overline{C}\cap S|=2$, say $c_{i},c_{j}\in S$, where $i,j\in[k]$ (with
$i=j$ when $c^{1}_{i},c^{2}_{i}\in S$), then $x_{i}$ (resp. $x_{j}$) is not a
member of $S$ and is open-dominated by only $c_{j}$ (resp. $c_{j}$). Hence,
both $x_{i}$ and $x_{j}$ are open-dominated exactly once each by $S$, and thus
$S$ is not an $OLD_{oind}$-set.

∎

In the following results we consider the existence of an $OLD_{oind}$-set in a
$P_{4}$-tidy graph. If $G$ is a disconnected $P_{4}$-tidy graph having an
$OLD_{oind}$-set, then each component of $G$ has an $OLD_{oind}$-set. Thus we
may consider only connected $P_{4}$-tidy graphs.

######  Theorem 3.4.

Let $G$ be a co-connected $P_{4}$-tidy graph. $G$ has an $OLD_{oind}$-set if
and only if $G$ is isomorphic to either $P_{5}$ or to the graph $Z$ shown in
Fig. 3(d).

###### Proof.

It can be verified by inspection that $P_{5}$ and $Z$ are co-connected
$P_{4}$-tidy graphs having $OLD_{oind}$-sets. Let $G$ be a co-connected
$P_{4}$-tidy graph. By Theorem 3.1, $G$ is a spider, a quasi-spider or one of
the graphs $C_{5}$, $P_{5}$ and $\overline{P_{5}}$. Suppose that $G$ has an
$OLD_{oind}$-set. Clearly, $G$ is not isomorphic to either $C_{5}$ or
$\overline{P_{5}}$. By Theorems 3.2 and 3.3 $G$ is isomorphic to the graph
$Z$. ∎

######  Theorem 3.5.

Let $G$ be a connected $P_{4}$-tidy graph of order $n\geq 2$. $G$ has an
$OLD_{oind}$-set if and only if $G$ is isomorphic to one of the graphs
$K_{2}$, $K_{3}$, $P_{5}$, $P_{5}\bowtie K_{1}$, $Z$, and $Z\bowtie K_{1}$ or
it can be obtained from them recursively by applying the following operation:
Let $t\geq 2$ and $G_{1},\ldots,G_{t}$ be connected $P_{4}$-tidy graphs each
having an $OLD_{oind}$-set. Set $G:=(G_{1}\oplus\cdots\oplus G_{t})\bowtie
K_{1}$.

###### Proof.

Clearly, $K_{2}$, $K_{3}$, $P_{5}$, $P_{5}\bowtie K_{1}$, $Z$, and $Z\bowtie
K_{1}$ are connected $P_{4}$-tidy graphs each having an $OLD_{oind}$-set.
Suppose instead that $G\notin\\{K_{2},K_{3},P_{5},P_{5}\bowtie
K_{1},Z,Z\bowtie K_{1}\\}$. Let $G_{1},\ldots,G_{t}$ be graphs such that
$G_{i}$ has an $OLD_{oind}$-set $S_{i}$, for each $i\in[t]$ and let $G$ be a
graph obtained by the described operation. Let $S=\bigcup_{i\in[t]}S_{i}$ and
$V(K_{1})=\\{v\\}$. It is easy to see that every vertex in
$V(G)\setminus\\{v\\}$ is both distinguished and open-dominated by $S$, and
that $v$ is the only vertex of $G$ that is adjacent to all the vertices of
$S$. Hence $S$ is also an $OLD_{oind}$-set of $G$.

Conversely, suppose that $G$ is a connected $P_{4}$-tidy graph distinct from
$K_{2}$ and $K_{3}$ such that $G$ has an $OLD_{oind}$-set $S$. Hence $n\geq
4$. If $\overline{G}$ is connected, $G$ is co-connected and by Theorem 3.4,
$G$ is isomorphic to one of $P_{5}$ and $Z$. If $\overline{G}$ is
disconnected, $G$ can be obtained by the join of two graphs, say $H_{1}$ and
$H_{2}$. Firstly, we claim that one of $H_{1}$ and $H_{2}$ has exactly one
vertex $v$ say, and $v\notin S$. To the contrary, suppose $S_{1}=S\cap
V(H_{1})\neq\emptyset$ and $S_{2}=S\cap V(H_{2})\neq\emptyset$. In order to be
open-independent $|S_{1}|=|S_{2}|=1$, and $|S|=2$, which implies that $G$ has
at most three vertices. Thus, one of $H_{1}$ and $H_{2}$ has an empty
intersection with $S$. Without loss of generality, we may assume $V(H_{2})\cap
S=\emptyset$. If $H_{2}$ has at least two vertices $u$ and $v$ say, then
$N_{G}(u)\cap S=N_{G}(v)\cap S$ which contradicts the fact that $S$ is an
$OLD$-set of $G$. So $H_{2}$ is isomorphic to $K_{1}$ and, $S=S_{1}$ is an
$OLD_{oind}$-set of $H_{1}$.

We now analyze the possibilities for $H_{1}$. First suppose that $H_{1}$ is
connected. If $|S|=2$, $G$ has at most three vertices. Since $n\geq 4$,
$|S|\geq 4$. Observe that, if $H_{1}$ is the join of two graphs, the vertices
in $S$ must belong to the same subgraph and any vertex of the another subgraph
is adjacent to every vertex of $S$. Altogether, these facts imply that there
exists a vertex in $H_{1}$, $y$ say, such that $S\subseteq N_{H_{1}}(y)$. In
this case, $v$ and $y$ are not distinguished by $S$ in $G$. Thus we may assume
that $H_{1}$ is co-connected. By Theorem 3.4, $H_{1}$ is isomorphic either to
$P_{5}$ ($G=P_{5}\bowtie K_{1}$) or $Z$ ($G=Z\bowtie K_{1}$). Now instead,
assume that $H_{1}$ is disconnected. In this case $H_{1}=G_{1},\ldots,G_{t}$
is a collection of $t\geq 2$ connected $P_{4}$-tidy graphs. As every vertex in
$V(G_{i})$ has exactly one additional neighbor in $G$ (i.e. vertex $v\notin
S$), if there exists $i\in[t]$ such that $G_{i}$ does not have an
$OLD_{oind}$-set, it is easy to see that $S$ is not an $OLD_{oind}$-set of
$G$. Thus, we can conclude that every $G_{i}$ with $i\in[t]$ has an
$OLD_{oind}$-set and that $G$ is the graph $H_{1}\bowtie K_{1}$. ∎

A _cograph_ is a graph that can be constructed from a given solitary vertex
using the repeated application of the disjoint union and join operations.
Another standard characterization of cographs is that they are those graphs
that do not contain a four-vertex-path as an induced subgraph. All complete
graphs, complete bipartite graphs, cluster graphs and threshold graphs are
cographs. Since any cograph $G$ has the property that either $G$ or
$\overline{G}$ is disconnected, we can conclude that any cograph having an
$OLD_{oind}$-set can be obtained from either $K_{2}$ or $K_{3}$ by the
operations described in Theorem 3.5. Hence, Corollary 3.6 follows.

######  Corollary 3.6.

Let $G$ be a connected cograph of order $n\geq 2$. $G$ has an $OLD_{oind}$-set
if and only if $G$ is isomorphic to one of the graphs $K_{2}$ and $K_{3}$ or
it can be obtained from them recursively by applying the following operation:
Let $t\geq 2$ and $G_{1},\ldots,G_{t}$ be connected cographs each having an
$OLD_{oind}$-set. Set $G:=(G_{1}\oplus\cdots\oplus G_{t})\bowtie K_{1}$.

##  4 Complementary prisms of cographs

In Corollary 3.6 we have a characterization of the class of cographs that have
an $OLD_{oind}$-set. Now we consider $OLD_{oind}$-sets in the complementary
prisms of cographs. If $G$ is a cograph then $\overline{G}$ and
$G\oplus\overline{G}$ are also cographs. However, if $G$ is a nontrivial
cograph, $G\overline{G}$ is not a cograph. Also, $G\overline{G}$ is a
$P_{7}$-free graph for a cograph $G$.

If $G$ is a connected cograph, then $\overline{G}$ is disconnected. We assume
that $G$ is a connected cograph and denote by
$\overline{G_{1}},\overline{G_{2}},\ldots,\overline{G_{t}}$ the connected
components of $\overline{G}$ and by $G_{1},G_{2},\ldots,G_{t}$; the
anticomponents of $G$. We denote by $|G_{i}|$ (resp. $|\overline{G_{i}}|$) the
number of vertices of the subgraph $G_{i}$ (resp. $\overline{G_{i}}$). There
are infinite families of cographs that have complementary prisms with
$OLD_{oind}$-sets, for example, the family described in Theorem 4.1.

######  Theorem 4.1.

[5] If $G$ is a nontrivial graph with a unique universal vertex, then
$G\overline{G}$ has an $OLD_{oind}$-set if and only if
$G=K_{1}\bowtie\overline{mK_{2}}$, where $m\geq 1$.

Cappelle et al. [5] reported some properties of an $OLD_{oind}$-set of a
complementary prism $G\overline{G}$. For instance, they proved that in any
$OLD_{oind}$-set in this class of graphs there is at most one edge that
directly connects a vertex in $V(G)$ with a vertex in $V(\overline{G})$. The
authors also proved in [2] that, given a general graph $G$, deciding whether
or not $G\overline{G}$ has an $OLD_{oind}$-set is an $\mathcal{NP}$-complete
problem. However, the special case where $G$ has girth of at least four can be
decided in polynomial time. Next, we show that the connected cographs having
an $OLD_{oind}$-set $S$ such that $|S\cap V(G)|=1$ are exactly those described
in Theorem 4.1.

######  Theorem 4.2.

Let $G$ be a nontrivial connected cograph such that $G\overline{G}$ has an
$OLD_{oind}$-set $S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$. Then $|S_{0}|=1$ if and only if
$G=K_{1}\bowtie\overline{mK_{2}}$, where $m\geq 1$.

###### Proof.

If $G=K_{1}\bowtie\overline{mK_{2}}$, where $m\geq 1$, it is easy to see that
$G\overline{G}$ has an $OLD_{oind}$-set $S_{0}\cup\overline{S}_{1}$ say, where
$\overline{S}_{1}=V(\overline{G})$ and $S_{0}$ contains only a universal
vertex of $G$. Therefore, $|S_{0}|=1$. For the converse, suppose $G$ is such
that $G\overline{G}$ has an $OLD_{oind}$-set $S_{0}\cup\overline{S}_{1}$ with
$|S_{0}|=1$, where $S_{0}=\\{v\\}$, say. Since $G$ is nontrivial it has at
least two vertices and every vertex in $V(G)\setminus\\{v\\}$ has at most one
neighbour in $\overline{S}_{1}$. In order to be dominated at least twice, the
neighbour must be in $N_{G}(v)$ and thus, $v$ is a universal vertex of $G$. By
Theorem 4.1, $\overline{G}=K_{1}\oplus mK_{2}$, where $m\geq 1$. ∎

By Theorem 4.1, if $G$ is a nontrivial cograph with a unique universal vertex,
then $G\overline{G}$ has an $OLD_{oind}$-set if and only if,
$|\overline{G_{i}}|=1$, for a unique $i$, where $1\leq i\leq t$ and
$|\overline{G_{i}}|=2$, otherwise. If a cograph $G$ does not have a universal
vertex, then $|\overline{G_{i}}|\geq 2$, $i\in[t]$. In this case, we show that
if $G\overline{G}$ has an $OLD_{oind}$-set $S$ at least one, and at most
three, components of $\overline{G}$ have at least three vertices. Let
$S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$. We consider the case $|S_{0}|=2$
in Theorem 4.5 and the general case in Theorem 4.6. For each component
$\overline{G_{i}}$ of $\overline{G}$, let
$\overline{D_{i}}=\overline{G_{i}}\setminus\overline{S}_{1}$ and
$\overline{D}=\bigcup_{i\in[t]}\overline{D_{i}}$. Let $D_{i}$ (resp. $D$) be
the corresponding vertices of $\overline{D_{i}}$ (resp. $\overline{D}$) in
$G_{i}$ (resp. $G$), with $S_{0}\subseteq D$. Let $n_{i}=|V(G_{i})|$.

######  Lemma 4.3.

If $G$ is a connected cograph such that $|\overline{G_{i}}|\geq 2$, $i\in[t]$,
where $t\geq 2$, and that $G\overline{G}$ has an $OLD_{oind}$-set
$S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$, then the following statements
hold:

  1. (i)

$S_{0}\neq\emptyset$ and $\overline{S}_{1}\neq\emptyset$.

  2. (ii)

For each $i\in[t]$, $V(\overline{G_{i}})\cap\overline{S}_{1}\neq\emptyset$.

  3. (iii)

Let $i\in[t]$. If $n_{i}\geq 3$ and $|S_{0}\cap V(G_{i})|\leq 1$, then
$\overline{D_{i}}$ is an independent set of $\overline{G}$ with
$1\leq|\overline{D_{i}}|\leq 2$.

  4. (iv)

If $|S_{0}|=2$, then there are two anticomponents $G_{i}$ and $G_{j}$ of $G$
with nonempty intersection with $S_{0}$, and $n_{i},n_{j}\geq 3$. Moreover,
$2\leq|\overline{D}|\leq 3$.

  5. (v)

There exists at most one $i\in[t]$ such that $n_{i}\geq 3$ and $S_{0}\cap
V(G_{i})=\emptyset$.

  6. (vi)

$\overline{G}$ has at least one and at most three components of size at least
three.

###### Proof.

We prove each item separately.

  1. _(i)_

For a proof by contradiction, suppose $S_{0}=\emptyset$. Let $v\in V(G)$. By
Theorem 2.2, vertex $v$ has to be open-dominated at least twice. Since $v$ has
at most one neighbor in $\overline{S}_{1}$, we can conclude that $S$ is not an
$OLD_{oind}$-set in $G\overline{G}$. The proof for $\overline{S}_{1}$ follows
analogously.

  2. _(ii)_

For a proof by contradiction, suppose there is $i\in[t]$ such that
$V(\overline{G_{i}})\cap\overline{S}_{1}=\emptyset$. Let $\overline{v}\in
V(\overline{G_{i}})$. By Theorem 2.2, vertex $\overline{v}$ has to be open-
dominated at least twice. Since $\overline{v}$ has at most one neighbor in
${S}_{0}$, we can conclude that $S$ is not an $OLD_{oind}$-set in
$G\overline{G}$.

  3. _(iii)_

If $\overline{D_{i}}$ is empty, by connectivity, $\overline{G_{i}}$ is
isomorphic to $K_{2}$ and thus $n_{i}=2$. Suppose $|\overline{D_{i}}|\geq 3$.
Then the vertices in $D_{i}$ have the same neighborhood as $G\setminus
V(G_{i})$. Since $|V(G_{i})\cap S_{0}|\leq 1$, $D_{i}$ has at least two
vertices that are not distinguished by $S$. Now, suppose that
$\overline{D_{i}}$ has two vertices and they are adjacent in $\overline{G}$.
So, the vertices in $D_{i}$ are not adjacent in $G_{i}$; if one of them is a
member of $S_{0}$ the other vertex is dominated once, since by open-
independence $S_{0}$ can have only one vertex of another anticomponent $G_{j}$
say, with $i\neq j$. If none of them is a member of $S_{0}$, they have the
same neighborhood in $S_{0}$. Therefore, these two vertices are not
distinguished by $S$.

  4. _(iv)_

Suppose $|S_{0}|=2$. We first prove that there are two anticomponents $G_{i}$
and $G_{j}$ of $G$ with nonempty intersection with $S_{0}$, and
$n_{i},n_{j}\geq 3$. For a proof by contradiction, suppose that there is an
unique anticomponent $G_{i}$ of $G$ with $|G_{i}\cap S_{0}|=2$. Let
$S_{0}=\\{u,v\\}$. Since $G_{i}$ is disconnected, there is a vertex $z\in
V(G_{i})$ that is adjacent to neither $u$ nor $v$. Since $z$ has at most one
neighbor in $\overline{S}_{1}$, it follows that $S$ is not an
$OLD_{oind}$-set. Now, suppose that $|V(G_{i})\cap S_{0}|=1$ and that
$n_{i}=2$. Let $V(G_{i})=\\{u,v\\}$. Without loss of generality, assume
$S_{0}=\\{u\\}$. If $\overline{u}\in\overline{S}_{1}$, then
$\overline{v}\notin\overline{S}_{1}$ and $\overline{v}$ is dominated once by
$S$, contradicting the fact that $S$ is an $OLD_{oind}$-set of
$G\overline{G}$. If $\overline{u}\notin\overline{S}_{1}$, since it has to be
dominated twice, $\overline{v}\in\overline{S}_{1}$ and by open-independence,
$v\in S_{0}$. Thus $u,v\in S_{0}$, which contradicts that there are two
anticomponents $G$ with nonempty intersection with $S_{0}$.

Now we prove that $2\leq|\overline{D}|\leq 3$. By the first part of the proof,
there are two anticomponents of ${G}$, say $G_{i}$ and $G_{j}$, having
nonempty intersection with $S_{0}$, and both have size at least three. Since
$|\overline{D_{i}}|,|\overline{D_{j}}|\geq 1$, it follows that
$|\overline{D}|\geq 2$. For the upper bound, since $|S_{0}\cap V(G_{k})|\leq
1$, for every $k\in[t]$, by Lemma 4.3 (iii) the vertices of $\overline{D}_{k}$
are independent in $\overline{G}$. Also, as the vertices of the distinct
components of $\overline{G}$ are not adjacent, $\overline{D}$ is an
independent set of $\overline{G}$ and ${D}$ induces a complete graph in $G$.
If $|D|\geq 4$, since at most two of these vertices are in $S_{0}$, and they
have no neighbors in $\overline{S}_{1}$, the remainder (at least two vertices)
are not distinguished by $S$.

  5. _(v)_

Suppose that there are two anticomponents of $G$ of order at least 3, say
$G_{i}$ and $G_{j}$, that do not have vertices in common with $S_{0}$. By
(iii), $|{D}_{i}\cup{D}_{j}|\geq 2$. However, the vertices in $D_{i}\cup
D_{j}$ are not distinguished by $S_{0}$, since they have the same neighborhood
in $G\setminus(V(G_{i})\cup V(G_{j}))$.

  6. _(vi)_

Firstly, suppose that each component of $\overline{G}$ is a $K_{2}$. By (i),
$S_{0}\neq\emptyset$. So suppose $v\in V(G_{i})$ such that $v\in S_{0}$. If
$\overline{v}\in\overline{S}_{1}$, its unique neighbor in $\overline{G}$,
$\overline{u}$ say, does not belong to $\overline{S}_{1}$ and then, in order
to dominate $\overline{u}$ twice, $u\in S_{0}$. This implies that $u$ has
another neighbor in $S_{0}$, in an anticomponent different from $G_{i}$, which
contradicts the assumption that $S$ is open-independent. If
$\overline{v}\notin\overline{S}_{1}$, the vertex $\overline{u}$ is in
$\overline{S}_{1}$ and we have an analogous situation. Thus, it can be
concluded that $S_{0}=\emptyset$, which contradicts the premise of (i).
Therefore, $\overline{G}$ has at least one component of size at least three.
Secondly, for a proof by contradiction, suppose that at least four components
of $\overline{G}$ have size at least three. Since the elements of $S_{0}$ are
open-independent, $S_{0}$ contains vertices that are members of at most two
distinct anticomponents of $G$. Thus, there are at least two anticomponents of
$G$ with order at least 3, say $G_{i}$ and $G_{j}$, that do not have vertices
in common with $S_{0}$. By (v), $S$ is not an $OLD_{oind}$-set.

∎

For $\ell,m\geq 1$, we denote by $R_{\ell,m}$ the graph
$\overline{K_{\ell}}\bowtie mK_{2}$ that contains $\ell+2m$ vertices.
$R^{*}_{\ell,m}$ denotes the graph obtained from $R_{\ell,m}$ with one edge
missing between one vertex of $\overline{K_{\ell}}$ and exactly one copy of
$K_{2}$. Note that $R_{\ell,m}$ is a cograph, and for $\ell=1,2$,
$R^{*}_{\ell,1}$ is also a cograph; $R_{1,1}$ is isomorphic to $K_{3}$; and
$R^{*}_{1,1}$ is isomorphic to $P_{3}$.

######  Lemma 4.4.

Let $G$ be a connected cograph such that $|\overline{G_{i}}|\geq 2$,
$i\in[t]$, where $t\geq 2$, and that $G\overline{G}$ has an $OLD_{oind}$-set
$S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$ and let $i\in[t]$ such that
$n_{i}\geq 3$.

  1. (i)

If $V(G_{i})\cap S_{0}=\emptyset$, then $\overline{G_{i}}\cong R_{1,m}$.

  2. (ii)

If $|V(G_{i})\cap S_{0}|=1$, then $\overline{G_{i}}$ is isomorphic to one of
$R^{*}_{\ell,1}$ and $R_{\ell,m}$, for $\ell=1,2$.

###### Proof.

To prove (i), suppose $n_{i}\geq 3$ and $V(G_{i}\cap S_{0}=\emptyset)$. By
Lemma 4.3 (ii), $V(\overline{G_{i}})\cap\overline{S}_{1}\neq\emptyset$. Let
$\overline{A_{i}}=V(\overline{G_{i}})\cap\overline{S}_{1}$. By Lemma 4.3
(iii), $\overline{D_{i}}$ induces an independent set with
$1\leq|\overline{D_{i}}|\leq 2$. The set $\overline{A_{i}}$ induces
$m=|\overline{A_{i}}|/2$ independent edges. Since $\overline{G_{i}}$ is
connected, at least one vertex of every edge induced by $\overline{A_{i}}$ has
a neighbor in $\overline{D_{i}}$. If $|\overline{D_{i}}|=2$, the two vertices
of $D_{i}$ are not distinguished by $S$, since they have the same neighborhood
in $G\setminus V(G_{i})$. Thus, we may assume $|\overline{D_{i}}|=1$ and let
$\overline{D_{i}}=\\{\overline{u}\\}$. If $m=1$, since $\overline{u}$ has at
least two neighbors in $\overline{S}_{1}$, it follows that $\overline{G}\cong
R_{1,1}$. If $m\geq 2$, we claim that $\overline{u}$ is adjacent to every
vertex in $\overline{A_{i}}$. Suppose that this is not true and consider an
edge $ab$ induced by vertices in $\overline{A_{i}}$ such that
$\overline{u}a\notin E(\overline{G_{i}})$. In this case, $ab\overline{u}c$ is
an induced 4-path in $\overline{G_{i}}$, where $c$ is an vertex of some other
edge induced by $\overline{A_{i}}$. So, $\overline{G_{i}}$ is not a cograph.
Therefore, $\overline{G_{i}}\cong R_{1,m}$.

Now, we prove (ii). By Lemma 4.3 (ii),
$V(\overline{G_{i}})\cap\overline{S}_{1}\neq\emptyset$. Let
$\overline{A_{i}}=V(\overline{G_{i}})\cap\overline{S}_{1}$. By Lemma 4.3
(iii), $\overline{D_{i}}$ induces an independent set with
$1\leq|\overline{D_{i}}|\leq 2$. The set $\overline{A_{i}}$ induces
$m=|\overline{A_{i}}|/2$ independent edges. Since $\overline{G_{i}}$ is
connected, at least one vertex incident with every edge induced by
$\overline{A_{i}}$ has a neighbor in $\overline{D_{i}}$. If $m=1$, we have
four possible cographs, $R^{*}_{\ell,1}$, $R_{\ell,1}$, for $\ell=1,2$. If
$m\geq 2$, we claim that every vertex in $\overline{D_{i}}$ is adjacent to
every vertex in $\overline{A_{i}}$. For a proof by contradiction, suppose that
this is not true and consider two edges $ab$ and $cd$, induced by vertices in
$\overline{A_{i}}$. Let $\overline{u}\in\overline{D_{i}}$. Without loss of
generality, suppose that $\overline{u}a\notin E(\overline{G_{i}})$, for an
edge $ab$ induced by vertices in $\overline{A_{i}}$. In this case,
$ab\overline{u}c$ is an induced 4-path in $\overline{G_{i}}$, where $c$ is an
vertex of some other edge induced by $\overline{A_{i}}$. So,
$\overline{G_{i}}$ is not a cograph. Therefore, $\overline{G_{i}}$ is
isomorphic to $R_{\ell,m}$, for $\ell=1,2$. ∎

Next, we present in Theorems 4.5 and 4.6 a general recursive characterization
of the class $C$ of connected cographs such that if $G$ is a member of $C$
then $G\overline{G}$ has an $OLD_{oind}$-set. Theorem 4.5 (4.6) is illustrated
in Figure 4(a) (4(b)).

######  Theorem 4.5.

Let $G$ be a connected cograph such that $|\overline{G_{i}}|\geq 2$, $i\in[t]$
with $t\geq 2$. $G\overline{G}$ has an $OLD_{oind}$-set
$S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$ such that $|S_{0}|=2$ if and only
if there are at least two, and at most three, components $\overline{G_{i}}$
with $n_{i}\geq 3$ and each component of $\overline{G}$ is isomorphic to one
of the graphs $K_{2}$, $R^{*}_{\ell,1}$ and $R_{\ell,m}$, for $\ell=1,2$ and
$m\geq 1$, with the following further conditions:

  1. (i)

at most one component of $\overline{G}$ is either $R^{*}_{2,1}$ or $R_{2,m}$
and if $\overline{G}$ has such a component, $\overline{G}$ has exactly two
components of size at least three; and

  2. (ii)

at most two components of $\overline{G}$ are isomorphic to $R^{*}_{1,1}$,
$R^{*}_{2,1}$ or $R_{2,m}$.

###### Proof.

Suppose $G$ is as described and that $G\overline{G}$ has an $OLD_{oind}$-set
$S=S_{0}\cup\overline{S}_{1}$ with $S_{0}\subseteq V(G)$,
$\overline{S}_{1}\subseteq V(\overline{G})$, and $|S_{0}|=2$. Let $t^{\prime}$
be the number of components of $\overline{G}$ of size at least three. By Lemma
4.3 (vi), $t^{\prime}\leq 3$. By Lemma 4.3 (iv), two anticomponents of $G$
have nonempty intersection with $S_{0}$ and both have size at least three,
thus $2\leq t^{\prime}\leq 3$.

Since $|V(G_{i})\cap S_{0}|\leq 1$, for every component $\overline{G_{i}}$ of
$\overline{G}$ with $n_{i}\geq 3$, by Lemma 4.4 (ii) the components of
$\overline{G}$ of size at least three are $R^{*}_{\ell,1}$ or $R_{\ell,m}$,
for $\ell=1,2$. To prove (i), first suppose that there are at least two
components of $\overline{G}$ that are one of the graphs $R^{*}_{2,1}$ and
$R_{2,m}$, say $\overline{G_{i}}$ and $\overline{G_{j}}$. By Lemma 4.3 (iii),
$\overline{D_{i}}$ (resp. $\overline{D_{j}}$) is independent with size at
least one and at most two. If $|\overline{D_{i}}|=1$ (resp.
$|\overline{D_{j}}|=1$) the remaining vertices of $\overline{G_{i}}$ (resp.
$\overline{G_{j}}$) cannot induce independent edges. Hence
$|\overline{D_{i}}|=|\overline{D_{j}}|=2$ which implies that
$|\overline{D}|\geq 4$. By Lemma 4.3 (iv), $|S_{0}|\neq 2$ contradicting the
premise of the theorem. Hence we can conclude that at most one component of
$\overline{G}$ is either $R^{*}_{2,1}$ or $R_{2,m}$. Secondly, suppose
$\overline{G}$ has exactly one component, say $\overline{G_{i}}$, which is
isomorphic to either $R^{*}_{2,1}$ or $R_{2,m}$. Thus $|\overline{D_{i}}|=2$.
Suppose that $\overline{G}$ has other two components, say $\overline{G_{j}}$
and $\overline{G_{p}}$, each one with size at least three. By Lemma 4.3 (iii),
$|\overline{D_{j}}\cup\overline{D_{p}}|\geq 2$. Since $|\overline{D_{i}}|=2$,
$|\overline{D}|\geq 4$. Again, by Lemma 4.3 (iv), $|S_{0}|\neq 2$
contradicting the premise of the theorem. This completes the proof of (i). Now
we prove (ii). If $t^{\prime}=3$, since $|S_{0}|=2$ one of the components of
$\overline{G}$ with size at least three, say $\overline{G_{j}}$, is such that
$G_{j}$ has empty intersection with $S_{0}$. Thus by Lemma 4.4 (i),
$\overline{G_{j}}\cong R_{1,m}$, which implies that at most two components of
$\overline{G}$ are isomorphic to the graphs $R^{*}_{1,1}$, $R^{*}_{2,1}$, and
$R_{2,m}$. The difference $t-t^{\prime}$ is the number of components of
$\overline{G}$ having size two. Clearly, each of these components (if any) is
isomorphic to $K_{2}$.

Conversely, suppose $G\overline{G}$ is as described, with at least two and at
most three components $\overline{G_{i}}$ with $n_{i}\geq 3$ and the components
of $\overline{G}$ are the graphs $K_{2}$, $R^{*}_{\ell,1}$, and $R_{\ell,m}$,
for $\ell=1,2$. Assume conditions (i) and (ii) hold. We show how to select the
two vertices in $S_{0}$ and the vertices in $\overline{S}_{1}$ such that
$S=S_{0}\cup\overline{S}_{1}$ is an $OLD_{oind}$-set of $G\overline{G}$. For
every component $\overline{G_{i}}$ of $\overline{G}$ there is a partition of
this vertex set into sets $\overline{D_{i}}$ and $\overline{M_{i}}$ such that
$\overline{D_{i}}$ is an independent set with
$|\overline{D_{i}}|\in\\{0,1,2\\}$ and $\overline{M_{i}}$ contains the $2m$
vertices of the $m\geq 1$ independent edges of $\overline{G_{i}}$. Let
$\overline{D_{i}}$ and $\overline{M_{i}}$ be such sets. Let
$\overline{D}=\bigcup_{i\in[t]}\overline{D_{i}}$. So,
$\overline{S}_{1}=\bigcup_{i\in[t]}M_{i}=\overline{M}$. Let $D_{i}$, $M_{i}$,
$D$, and $M$ be the sets of corresponding vertices in $G$. Note that in $G$,
every vertex in $M$ has a different neighbor in $\overline{M}$. Since we shall
show that $S_{0}$ has vertices in two distinct anticomponents, every vertex of
$G$ has at least one neighbor in $S_{0}$. Hence, the vertices in
$M\cup\overline{M}$ are distinguished and open-dominated by $S$ and we need to
consider only the vertices in $D\cup\overline{D}$.

We proceed by setting the vertices in $S_{0}$. We first consider the case
$t^{\prime}=2$. Without loss of generality, assume $|G_{1}|,|G_{2}|\geq 3$.
Since conditions (i) and (ii) hold, by symmetry we assume
$\overline{G_{1}}\in\\{R^{*}_{1,1},R^{*}_{2,1},R_{1,m},R_{2,m}\\}$ and
$\overline{G_{2}}\in\\{R^{*}_{1,1},R_{1,m}\\}$.

If $|D_{1}|=1$, let $D_{1}=\\{v\\}$. If $|D_{1}|=2$ and $\overline{G_{1}}$ is
isomorphic to $R^{*}_{2,1}$, let $D_{1}=\\{u,v\\}$ with $v$ being the vertex
of degree two in $G_{1}$. If $|D_{1}|=2$ and $\overline{G_{1}}$ is isomorphic
to $R_{2,m}$, let $D_{1}=\\{u,v\\}$. Let $\overline{u},\overline{v}$ be the
corresponding vertices of $u,v$ in $\overline{G_{1}}$. In all cases, we set
$v\in S_{0}$. We analyze the following cases:

  1. 1.

If $\overline{G_{1}}$ is isomorphic to $R^{*}_{1,1}$, then $\overline{v}$ has
one neighbor in $\overline{M_{1}}$ and $v\in N_{G}(\overline{v})$.

  2. 2.

If $\overline{G_{1}}$ is isomorphic to $R^{*}_{2,1}$, then $\overline{u}$ has
two neighbors in $\overline{M_{1}}$ and $\overline{v}$ has exactly one
neighbor in $\overline{M_{1}}$. Since $v\in S_{0}$, $\overline{u}$ and
$\overline{v}$ are open-dominated twice and distinguished by $S$.

  3. 3.

If $\overline{G_{1}}$ is isomorphic to $R_{2,m}$, then $\overline{u}$ and
$\overline{v}$ are both neighbors of every vertex in $\overline{M_{1}}$. Since
$v\in S_{0}$, these two vertices are open-dominated and distinguished by $S$.

  4. 4.

If $\overline{G_{1}}$ is isomorphic to $R_{1,m}$, then $\overline{v}$ is the
unique vertex that is the neighbor of all vertices of $M_{1}$.

As $\overline{G_{2}}\in\\{R^{*}_{1,1},R_{1,m}\\}$, $|D_{2}|=1$. Let
$D_{2}=\\{v\\}$. We set $v\in S_{0}$. We have two possibilities for
$\overline{G_{2}}$ that are analogous to the cases 1 and 4, described above.
We can conclude that all vertices in $\overline{G}$ are distinguished and
open-dominated by $S$, and $S$ is open-independent.

Now we consider the vertices in $D$. Since at most one component of
$\overline{G}$ is isomorphic to either $R^{*}_{2,1}$ or $R_{2,m}$, it follows
that $2\leq|D|\leq 3$. Two of these vertices are in $S_{0}$. So there is at
most one vertex of $G$, $z$ say, such that neither $z$ nor $\overline{z}$ is
in $S$. The choosing of $S_{0}$ guarantees that $z$ is the only vertex of $G$
that is dominated exclusively by $S_{0}$.

Finally, we consider the case $t^{\prime}=3$. Without loss of generality, we
assume that $|G_{j}|\geq 3$, for every $j\in[3]$. Since conditions (i) and
(ii) hold, and by symmetry, we assume that
$\overline{G_{1}},\overline{G_{2}}\in\\{R^{*}_{1,1},R_{1,m}\\}$ and
$\overline{G_{3}}$ is isomorphic to $R_{1,m}$. Thus, $|D_{1}|=|D_{2}|=1$ and
we set $S_{0}=D_{1}\cup D_{2}$.

As $\overline{G_{1}},\overline{G_{2}}\in\\{R^{*}_{1,1},R_{1,m}\\}$, we can use
similar arguments to those used in the case $t^{\prime}=2$ to conclude that
each vertex in $\overline{D_{1}}\cup\overline{D_{2}}$ is both dominated at
least twice and distinguished by $S$. Since $S_{0}=D_{1}\cup D_{2}$, these
vertices are distinguished by $S$. Again, the vertex in $D_{3}$ is the only
vertex of $G$ that is dominated exclusively by $S_{0}$. Therefore, $S$ is an
$OLD_{oind}$-set of $G\overline{G}$ with $|S_{0}|=2$. See Fig. 4(a) for an
example. ∎

$V(\overline{G})$ $G_{1}$ $G_{2}$ $G_{3}$$V(G)$ (a) The components of
$\overline{G}$ are the graphs $R_{2,2}$, $R^{*}_{1,1}$, and $K_{2}$.

$V(\overline{G})$ $G_{1}$ $G_{2}$ $G_{3}$$V(G)$ (b) $G$ can be obtained
recursively from ${K_{1}\bowtie\overline{2K_{2}}}$.
$G=\overline{\overline{\overline{\overline{K_{1}\bowtie\overline{2K_{2}}}\bowtie\overline{K_{2}}}\bowtie\overline{K_{2}}}\bowtie\overline{R_{1,1}}}\bowtie\overline{R_{1,1}}\bowtie\overline{K_{2}}=((((K_{1}\bowtie\overline{2K_{2}})\oplus
K_{2})\bowtie\overline{K_{2}})\oplus{R_{1,1}})\bowtie\overline{R_{1,1}}\bowtie\overline{K_{2}}$.

Figure 4: Complementary prisms of cographs having $OLD_{oind}$-sets. 4(a)
illustrates Theorem 4.5 and 4(b) represents Theorem 4.6. An edge between two
rectangles indicates complete adjacency between vertices.

######  Theorem 4.6.

$G$ is a connected cograph such that $G\overline{G}$ has an $OLD_{oind}$-set
if and only if $G$ is isomorphic to one of the graphs
${K_{1}\bowtie\overline{sK_{2}}}$, $s\geq 1$, and graph ${G}$ described in
Theorem 4.5, or it can be obtained from them recursively by the following
operation: let $H$ be a connected cograph such that $H\overline{H}$ has an
$OLD_{oind}$-set. Set $G=\overline{H}\bowtie F\bowtie(\overline{rK_{2}})$,
where $F\in\\{\overline{R_{1,m}},\overline{K_{2}}\\}$, $r\geq 0$, $m\geq 1$.

###### Proof.

Suppose that $G$ is a connected cograph such that $G\overline{G}$ has an
$OLD_{oind}$-set $S=S_{0}\cup\overline{S}_{1}$ where $S_{0}\subseteq V(G)$ and
$\overline{S}_{1}\subseteq V(\overline{G})$. Assume that $\overline{G}$ has
components $\overline{G_{1}}\ldots,\overline{G}_{t}$, with $t\geq 2$. By Lemma
4.3 (i), $S_{0}$ is nonempty. If $|S_{0}|=1$, then by Theorem 4.2, ${G}$ is
the graph ${K_{1}\bowtie\overline{sK_{2}}}$, and if $|S_{0}|=2$, then $G$ is
the graph described in Theorem 4.5. So we may assume that $|S_{0}|\geq 3$. By
Lemma 4.3 (vi), at least one and at most three components of $\overline{G}$
have at least three vertices. Since $|S_{0}|\geq 3$, there exists exactly one
anticomponent $G_{i}$ say, of $G$ with nonempty intersection with $S_{0}$. (If
this were not so, since every vertex of $G_{i}$ is adjacent to every vertex of
any other anticomponent $G_{p}$ with $p\neq i$, then $S$ would not be an open-
independent set.) By Lemma 4.3 (v), there exists at most one anticomponent
$G_{i}$ of $G$ with size at least three with empty intersection with $S_{0}$,
which implies that $G$ has at most two anticomponents $G_{i}$ with size at
least three. If $G$ has an anticomponent $G_{i}$ of size at least three having
empty intersection with $S_{0}$, by Lemma 4.4 (i), this anticomponent is
isomorphic to $\overline{R_{1,m}}$. Otherwise, if $|G_{i}|=2$, then $G_{i}$ is
isomorphic to $\overline{K_{2}}$. Without loss of generality, we assume that
$G_{1}$ is an anticomponent of $G$ with $S_{0}\subseteq V(G_{1})$ and $G_{2}$
is an anticomponent that can be isomorphic either to $\overline{R_{1,m}}$ or
to $\overline{K_{2}}$. Note that, each of the $t-2$ anticomponents of $G$ (if
any) is isomorphic to $\overline{K_{2}}$. So, until now, we have that
$G=G_{1}\bowtie G_{2}\bowtie(\overline{rK_{2}})$, with $r\geq 0$, for some
disconnected graph $G_{1}$ (since $\overline{G_{1}}$ is connected). Now,
suppose that $G_{1}\overline{G_{1}}$ does not have an $OLD_{oind}$-set. Thus
$S^{\prime}=S\cap V(G_{1}\overline{G_{1}})$ is not an $OLD_{oind}$-set of
$G_{1}\overline{G_{1}}$, and there is a vertex say $v$, of
$G_{1}\overline{G_{1}}$ that is not distinguished or open-dominated by
$S^{\prime}$. Since $S_{0}\subseteq V(G_{1})$ and there is no edge between
$\overline{G_{1}}$ and any other component of $\overline{G}$, we have that
$N_{G\overline{G}}(v)\cap S\subseteq V(G_{1}\cup\overline{G_{1}})$. This
implies that $v$ is not distinguished or dominated by $S$ and hence, $S$ is
not an $OLD_{oind}$-set of $G\overline{G}$. Therefore, $G$ can be obtained by
the described operation from a disconnected graph $G_{1}$ such that
$G_{1}\overline{G_{1}}$ has an $OLD_{oind}$-set.

Conversely, suppose that $G$ is a connected cograph obtained by the described
conditions. Since, by Theorem 4.2, ${K_{1}\bowtie\overline{sK_{2}}}$ has an
$OLD_{oind}$-set, and also the graph described in Theorem 4.5, we assume that
$G$ is none of these graphs. Hence we assume that $G=\overline{H}\bowtie
F\bowtie(\overline{rK_{2}})$ and $H$ is a connected cograph such that
$H\overline{H}$ has an $OLD_{oind}$-set $B=B_{0}\cup\overline{B}_{1}$ with
$B_{0}\subseteq V(H)$ and $\overline{B}_{1}\subseteq V(\overline{H})$. We show
how to select vertices of a set $S=S_{0}\cup\overline{S}_{1}$ where
$S_{0}\subseteq V(G)$ and $\overline{S}_{1}\subseteq V(\overline{G})$ such
that $S$ is an $OLD_{oind}$-set of $G\overline{G}$. We begin setting
$S_{0}=\overline{B}_{1}$ and $\overline{S}_{1}=B_{0}$. Hence, the vertices of
$H\cup\overline{H}$ are all distinguished and open-dominated by $S$ and we
need to consider only the remainder of the vertices. We lead with two cases.
First assume that $F$ is isomorphic to $\overline{R_{1,m}}$. In this case, we
must add to $\overline{S}_{1}$ the vertices that induce the $m$ independent
edges in $\overline{F}=R_{1,m}$. Let $\overline{v}$ be the universal vertex in
$\overline{F}$. Then $\overline{v}$ is dominated at least twice by vertices of
the $m\geq 1$ edges of $\overline{F}$ and it is the unique vertex with this
neighborhood in $S$. The vertices in $F$ are adjacent to all vertices in
$S_{0}$. Since $\overline{H}$ is disconnected and hence, $H\overline{H}$ has
an $OLD_{oind}$-set, by Lemma 4.3 (ii) $\overline{B}_{1}$ has at least one
vertex of each component of $\overline{H}$. Let $v$ be the neighbor of
$\overline{v}$ in $F$. Each vertex in $V(F)\setminus\\{v\\}$ has a distinct
neighbor in $\overline{S}_{1}$ and $v$ is the unique vertex whose neighborhood
in $S$ is exactly $S_{0}$. Observe that $\overline{B}_{1}$ has size at least
three and so is $S_{0}$. Now assume that $F$ is isomorphic to
$\overline{K_{2}}$. In this case we add the vertices of $\overline{F}=K_{2}$
to the set $\overline{S}_{1}$ and by using similar arguments to those in the
first case, it is easy to see that the vertices of $F$ are open-dominated and
distinguished by $S$. If $t\geq 3$, each of the $t-2$ other components of
$\overline{G}$ (if any) is isomorphic to $K_{2}$ and we proceed in the same
way as in the latter case. Therefore, $S$ is an $OLD_{oind}$-set of
$G\overline{G}$. See Fig. 4(b) for an example of a graph $G\overline{G}$
obtained by this operation from ${K_{1}\bowtie\overline{2K_{2}}}$. ∎

## References

  * Bendali-Braham et al. [2019] A. Bendali-Braham, N. Ikhlef-Eschouf, and M. Blidia.  Some results on the b-chromatic number in complementary prism graphs.  _RAIRO-Oper Res_ , 53(4):1187–1195, 2019.
  * [2] M. R. Cappelle, E. M. Coelho, L. R. Foulds, and H. J. Longo.  Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs.  submitted.
  * Cappelle et al. [2014] M. R. Cappelle, L. Penso, and D. Rautenbach.  Recognizing some complementary products.  _Theor Comput Sci_ , 521:1–7, 2014.  doi: 10.1016/j.tcs.2013.11.006.
  * Cappelle et al. [2015] M. R. Cappelle, E. M. M. Coelho, H. Coelho, L. D. Penso, and D. Rautenbach.  Identifying Codes in the Complementary Prism of Cycles.  _ArXiv e-prints_ , Jul 2015.  arXiv eprint 1507.05083.
  * Cappelle et al. [2019] M. R. Cappelle, E. M. Coelho, L. R. Foulds, and H. J. Longo.  Open-independent, open-locating-dominating sets in complementary prism graphs.  _Electronic Notes in Theoretical Computer Science_ , 346:253 – 264, 2019.  ISSN 1571-0661.  doi: https://doi.org/10.1016/j.entcs.2019.08.023.  Proceedings of the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).
  * Castonguay et al. [2019] D. Castonguay, E. M. Coelho, H. Coelho, and J. R. Nascimento.  On the geodetic number of complementary prisms.  _Inform Process Lett_ , 144:39–42, 2019.
  * Desormeaux and Haynes [2011] W. Desormeaux and T. Haynes.  Restrained domination in complementary prisms.  _Utilitas Math_ , 86:267–278, 2011.
  * Desormeaux et al. [2013] W. Desormeaux, T. Haynes, and L. Vaughan.  Double domination in complementary prisms.  _Utilitas Math_ , 91:131–142, 2013.
  * Duarte et al. [2017] M. A. Duarte, L. Penso, D. Rautenbach, and U. dos Santos Souza.  Complexity properties of complementary prisms.  _J Comb Optim_ , 33(2):365–372, 2017.  doi: 10.1007/s10878-015-9968-5.
  * Dyer and Frieze [1986] M. E. Dyer and A. M. Frieze.  Planar 3dm is np-complete.  _J Algorithm_ , 7(2):174–184, 1986.
  * Foucaud et al. [2017] 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.  _Theor Comput Sci_ , 668:43 – 58, 2017.  ISSN 0304-3975.  doi: https://doi.org/10.1016/j.tcs.2017.01.006.
  * Giakoumakis et al. [1997] V. Giakoumakis, F. Roussel, and H. Thuillier.  On p_4-tidy graphs.  _Discret Math Theor Comput Sci_ , 1:17–41, 1997.
  * Givens et al. [2019] R. M. Givens, G. Yu, and R. K. Kincaid.  Open locating-dominating sets in circulant graphs.  _Discussiones Mathematicae Graph Theory_ , 1(ahead-of-print), 2019.
  * Gongora et al. [2013] J. A. Gongora, T. Haynes, and E. Jum.  Independent domination in complementary prisms.  _Utilitas Math_ , 91:3–12, 2013.
  * Hammack et al. [2011] R. Hammack, W. Imrich, and S. Klavžar.  _Handbook of Product Graphs, Second Edition_.  Discrete Mathematics and Its Applications. CRC Press, second edition, 2011\.  ISBN 9781439813058.
  * Hartmanis [1982] J. Hartmanis.  Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson).  _Siam Rev_ , 24(1):90, 1982.
  * Haynes et al. [2007] T. Haynes, M. Henning, P. J. Slater, and L. C. van der Merwe.  The complementary product of two graphs.  _Bull Inst Comb Appl_ , 51:21–30, 2007.
  * Haynes et al. [2009a] T. Haynes, K. Holmes, D. Koessler, and L. Sewell.  Locating-domination in complementary prisms of paths and cycles.  _Congressus numerantium_ , 199:45–55, 2009a.
  * Haynes et al. [2009b] T. W. Haynes, M. A. Henning, and L. C. van der Merwe.  Domination and total domination in complementary prisms.  _J Comb Optim_ , 18(1):23–37, Jul 2009b.  doi: 10.1007/s10878-007-9135-8.
  * Holmes et al. [2010] K. R. S. Holmes, D. R. Koessler, and T. W. Haynes.  Locating-domination in complementary prisms.  _J Comb Math Comb Comput_ , 72:163–171, 2010.
  * Honkala et al. [2004] I. Honkala, T. Laihonen, and S. Ranto.  On locating-dominating codes in binary Hamming spaces.  _Discret Math Theor C_ , 6(2):265–282, 2004.
  * Karpovsky et al. [1998] M. G. Karpovsky, K. Chakrabarty, and L. B. Levitin.  On a new class of codes for identifying vertices in graphs.  _IEEE T Inform Theory_ , 44(2):599–611, 1998\.  doi: 10.1109/18.661507.
  * Kazemi [2011] A. P. Kazemi.  $k$-tuple total domination in complementary prisms.  _ISRN Discrete Math_ , 2011:1–13, 2011.  doi: 10.5402/2011/681274.  Article ID 681274.
  * Kincaid et al. [2015] R. Kincaid, A. Oldham, and G. Yu.  Optimal open-locating-dominating sets in infinite triangular grids.  _Discrete Appl Math_ , 193:139–144, 2015.
  * Laifenfeld et al. [2009] M. Laifenfeld, A. Trachtenberg, R. Cohen, and D. Starobinski.  Joint monitoring and routing in wireless sensor networks using robust identifying codes.  _Mob Netw Appl_ , 14(4):415–432, 2009.
  * Lobstein [2012] A. Lobstein.  Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography.  _Published electronically at https://www.lri.fr/ lobstein/debutBIBidetlocdom.pdf_ , 2012.
  * Lu et al. [2002] C. L. Lu, M.-T. Ko, and C. Y. Tang.  Perfect edge domination and efficient edge domination in graphs.  _Discrete Appl Math_ , 119(3):227–250, 2002.
  * Meierling et al. [2015] D. Meierling, F. Protti, D. Rautenbach, and A. R. de Almeida.  Cycles in complementary prisms.  _Discrete Appl Math_ , 193:180–186, 2015.
  * Ray et al. [2004] S. Ray, D. Starobinski, A. Trachtenberg, and R. Ungrangsi.  Robust location detection with sensor networks.  _IEEE J Sel Areas Commun_ , 22(6):1016–1025, 2004\.
  * Savić et al. [2018] A. L. Savić, Z. L. Maksimović, and M. S. Bogdanović.  The open-locating-dominating number of some convex polytopes.  _Filomat_ , 32(2):635–642, 2018.
  * Seo and Slater [2010] S. J. Seo and P. J. Slater.  Open neighborhood locating-dominating sets.  _Australas J Comb_ , 46:109–119, 2010.
  * Seo and Slater [2011] S. J. Seo and P. J. Slater.  Open neighborhood locating–dominating in trees.  _Discrete Appl Math_ , 159(6):484–489, 2011.
  * Seo and Slater [2017] S. J. Seo and P. J. Slater.  Open-independent, open-locating-dominating sets.  _Electronic Journal of Graph Theory and Applications_ , 5(2):179–193, 2017.  doi: 10.5614/ejgta.2017.5.2.2.
  * Zatesko et al. [2019] L. M. Zatesko, R. Carmo, A. L. Guedes, A. Zorzi, R. C. Machado, and C. M. Figueiredo.  On the chromatic index of complementary prisms.  _Acta Math Univ Comenianae_ , 88(3):1071–1077, 2019.