Error-correcting open-locating-dominating sets

Jean, Devin C.; Seo, Suk J.

doi:10.61091/cn235-03

Abstract

1. Introduction
2. Existence of ERR:OLD sets and extremal graphs
3. NP-Completeness of ERR:OLD minimization
3-SAT
ERR:OLD Minimization
4. ERR:OLD on infinite grids
Declarations

References

Congressus Numerantium

Volume 235
Pages: 23-40

Research article

Error-correcting open-locating-dominating sets

^¹, ^²

¹Vanderbilt University

²Middle Tennessee State University

Received: 15/04/2024
Accepted: 26/12/2024
Published: 11/02/2025

Copyright Link
License

Abstract

An open-locating-dominating set of a graph models a detection system for a facility with a possible “intruder” or a multiprocessor network with a possible malfunctioning processor. A “sensor” or “detector” is assumed to be installed at a subset of vertices where each can detect an intruder or a malfunctioning processor in its neighborhood, but not at its own location. We consider a fault-tolerant variant of an open-locating-dominating set called an error-correcting open-locating-dominating set, which can correct a false-positive or a false-negative signal from a detector. In particular, we prove the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. Additionally, we characterize the existence criteria for an error-correcting open-locating-dominating set in an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector and minimum error-correcting open-locating-dominating sets in infinite grids.

Keywords: system, open-locating-dominating sets, error-correction, cubic graphs, NP-completeness, extremal graphs, infinite grids

1. Introduction

Let $G$ be a graph with vertices $V (G)$ and edges $E (G)$ ; we assume that all graphs are simple, undirected, and connected. For notation, we let $n = | V (G) |$ , $m = | E (G) |$ , $d e g (v) = | {a b \in E (G) : v \in {a, b}} |$ , $δ (G) = min_{v \in V (G)} d e g (v)$ , and $Δ (G) = max_{v \in V (G)} d e g (v)$ . The open-neighborhood of a vertex $v \in V (G)$ , denoted $N (v)$ , is the set of all vertices adjacent to $v$ : ${w \in V (G) : v w \in E (G)}$ . The closed-neighborhood of a vertex $v \in V (G)$ , denoted $N [v]$ , is the set of all vertices adjacent to $v$ , as well as $v$ itself: $N (v) \cup {v}$ . A vertex set $S \subseteq V (G)$ is a (closed) dominating set if all vertices are within the closed neighborhood of some $v \in S$ ; that is, $\cup_{v \in S} N [v] = V (G)$ . Similarly, $S \subseteq V (G)$ is an open-dominating set if all vertices are within the open neighborhood of some $v \in S$ ; that is, $\cup_{v \in S} N (v) = V (G)$ .

Assume that $G$ models a facility with a possible “intruder” (or a multiprocessor network with a possible malfunctioning processor), where we want to be able to precisely determine the location of the intruder by placing (the minimum number of) detectors. Much work has been done on the topic of the graphical parameters involving various types of detectors. If a detector at $v$ can determine only whether or not the intruder is in $N [v]$ , then the detection system is called an identifying code (IC) as introduced by Karpovsky, Charkrabarty and Levitin [16]. A dominating set $S$ of $V (G)$ is an identifying code if for any any two distinct vertices $u, v \in V (G)$ , we have $N [u] \cap S \neq N [v] \cap S$ . If a detector at $v$ can determine only whether or not the intruder is in $N [v]$ but can differentiate $v$ from $N (v)$ , then the detection system is called a locating-dominating (LD) set, as introduced in Slater [25]. A dominating set $S$ of $V (G)$ is a locating-dominating set if for any two distinct vertices $u, v \in V (G) - S$ , we have $N (u) \cap S \neq N (v) \cap S$ .

This paper focuses on a detection system where a sensor at vertex $v$ can sense intruders at adjacent vertices (i.e., within $N (v)$ ), but not at $v$ itself. This type of detection system is called an open-locating-dominating (OLD) set, as introduced by Honkala, Laihonen and Ranto [11] and Seo and Slater [21]. An open-dominating set $S \subseteq V (G)$ is an open-locating-dominating set if for any two distinct vertices $u, v \in V (G)$ , we have $N (u) \cap S \neq N (v) \cap S$ . Additional recent work on variations of OLD sets with larger detection ranges includes Givens et al. [9]. Jean and Lobstein [12] have maintained a bibliography, currently with more than 500 entries, for work on detection system related topics.

For an OLD set $S \subseteq V (G)$ and $u \in V (G)$ , we let $N_{S} (u) = N (u) \cap S$ denote the (open) dominators of $u$ and $d o m (u) = | N_{S} (u) |$ denote the (open) domination number of $u$ . A vertex $v \in V (G)$ is $k$ -open-dominated by an open-dominating set $S$ if $| N_{S} (v) | \geq k$ . If $S$ is an open-dominating set and $u, v \in V (G)$ , $u$ and $v$ are $k$ -distinguished if $| N_{S} (u) △ N_{S} (v) | \geq k$ , where $△$ denotes the symmetric difference. If $S$ is an open-dominating set and $u, v \in V (G)$ , $u$ and $v$ are $k^{#}$ -distinguished if $| N_{S} (u) - N_{S} (v) | \geq k$ or $| N_{S} (v) - N_{S} (u) | \geq k$ .

The purpose of $k$ -domination in a detection system is to guarantee there are at least $k$ detectors monitoring each location in the graph simultaneously, which can allow for a level of basic fault tolerance. A fault-tolerant variant of an OLD set is called a redundant open-locating-dominating (RED:OLD) set which is resilient to a (single) detector being destroyed or going offline [23]. That is, an OLD set $S \subseteq V (G)$ is a RED:OLD set if $\forall v \in S$ , $S - {v}$ is an OLD set. For fault-tolerance beyond simple $k$ -redundancy, we conceptually establish that all detectors transmit either $0$ to represent the absence of an intruder, or $1$ to represent the presence of an intruder. A false negative is therefore when a detector incorrectly transmits a $0$ instead of a $1$ , while a false positive is when a detector incorrectly transmits a $1$ instead of a $0$ . An OLD set is called an error-detecting open-locating-dominating (DET:OLD) set if it can tolerant any single false negative [23]. Extending this, an OLD set is called an error-correcting open-locating-dominating (ERR:OLD) set, if it can tolerate any single false positive. The following theorem characterizes OLD, RED:OLD, DET:OLD, and ERR:OLD sets and they are useful in constructing those sets or verifying whether a given set meets their requirements.

Theorem 1.1. An open-dominating set is

(i) an OLD set if and only if every pair of vertices is 1-distinguished [14];

(ii) a RED:OLD set if and only if all vertices are 2-dominated and all pairs are 2-distinguished [23];

(iii) a DET:OLD set if and only if all vertices are 2-dominated and all pairs are $2^{#}$ -distinguished [23];

(iv) an ERR:OLD set if and only if all vertices are 3-dominated an all pairs are 3-distinguished.

In this paper, we will focus on the ERR:OLD parameter. As can be seen in Theorem 1.1, each new fault-tolerant capability on top of the basic OLD set demands stronger requirements for both the domination and distinguishing properties of the detector set. To see why the requirements for DET:OLD are not sufficient for ERR:OLD, consider the following two simple examples using detector set $S \subseteq V (G)$ . Firstly, if there is some 2-dominated vertex $v$ , with $N_{S} (v) = {p, q}$ , then an intruder at $v$ coupled with a false-negative at $p$ is indistinguishable from the absence of an intruder at $v$ coupled with a false-positive at $q$ . Thus, 2-domination is insufficient for an ERR:OLD set. And secondly, if there are two vertices $u, v$ with $N_{S} (u) \cap N_{S} (v) = {a, b}$ and $(u, v)$ are $2^{#}$ -distinguished with $N_{S} (v) - N_{S} (u) = {p, q}$ , then $(p, q, a, b)$ transmitting $(0, 1, 1, 1)$ could be due to a false-positive at $q$ (in which case the intruder is at $u$ ) or a false-negative at $p$ (in which case the intruder is at $v$ ). Thus, we cannot eliminate either of $u$ or $v$ as the intruder location, meaning $2^{#}$ -distinguishing is insufficient for an ERR:OLD. Indeed, it has been shown that an ERR:OLD set, or rather an equivalent error-correcting separating set, requires 3-domination and 3-distinguishing [24]. With both of these stronger properties, we see that two previous problem cases are resolved.

f1-1 — Figure 1 Optimal OLD (a), RED:OLD (b), DET:OLD (c), and ERR:OLD (d) sets. Detectors are darkened.

For finite graphs, the notations $OLD (G)$ , $RED:OLD (G)$ , $DET:OLD (G)$ , and ERR: OLD(G) represent the cardinality of the smallest possible OLD, RED:OLD, DET: OLD, and ERR:OLD sets on graph $G$ , respectively [23]. From Figure 1, which shows optimal solutions on the given graph which we will call $G$ , we see that $OLD (G) = 6$ , $RED:OLD (G) = 7$ , $DET:OLD (G) = 10$ , and $ERR:OLD (G) = 11$ .

In Section 2, we characterize the existence criteria for error-correcting open-locating-dominating sets in an arbitrary graph. We also consider extremal graphs that require every vertex to be a detector. In Section 3, we present a proof that the problem of finding a minimum error-correcting open-locating-dominating set in an arbitrary graph is NP-complete. We conclude with Section 4 by establishing bounds on the minimum densities of error-correcting open-locating-dominating sets on the infinite square grid, infinite triangular grid, and infinite king grid.

2. Existence of ERR:OLD sets and extremal graphs

In this section, we discuss the existence criteria of ERR:OLD sets and some extremal graphs. But before this, we will first present previous results on the existence criteria and some extremal graphs for the OLD, RED:OLD, and DET:OLD parameters. From Theorem 1.1, it is not hard to see the following relationships between the minimum cardinality of the four fault-tolerant OLD sets:

Observation 2.1. If

G

permits ERR:OLD, then

OLD (G) \leq RED:OLD (G) \leq DET:OLD (G) \leq ERR:OLD (G) .

OLD sets

From Theorem 1.1, by using $S = V (G)$ we can arrive at the following existence criteria for OLD on arbitrary graphs:

Theorem 2.2. [21] A graph

G

has an OLD set if and only if

G

satisfies

δ (G) \geq 1

and, whenever

u \neq v

N (u) \neq N (v)

Chellali et al. [2] proved the upper and lower bounds for $OLD (G)$ on arbitrary graphs:

Observation 2.3 [2] If graph

G

has an OLD set, then

2 \leq OLD (G) \leq n

The upper bound of $OLD (G) = n$ is achievable, and Foucaud et al. [7] later provided a full characterization for this class of extremal graphs:

Definition 2.4 . [6] For any

k \in N

, the half-graph,

H_{k}

is given by

V = {v_{1}, \dots, v_{k}} \cup {w_{1}, \dots, w_{k}}

and

E = {v_{i} w_{j} : i \leq j}

Theorem 2.5. [7]

OLD (G) = n

if and only if

G

is a half-graph.

Seo and Slater established the existence criteria for trees, determined the lower and upper bounds for $OLD (G)$ on trees, and fully characterized the extremal trees which achieve these upper and lower bounds [22].

Theorem 2.6. [22] A tree

T

of order

n \geq 2

has an OLD set if and only if every vertex is adjacent to at most one leaf.

Theorem 2.7. [22] If tree

T

has an OLD set, then

⌈ n / 2 ⌉ + 1 \leq OLD (G) \leq n - 1

Henning and Yeo [10] determined the upper bound on OLD(G) when G is a cubic graph.

Theorem 2.8. [10] If

G

is a twin-free cubic graph of order

n

, then

OLD (G) \leq \frac{3}{4} n

RED:OLD sets

From Theorem 1.1, by using $S = V (G)$ , we can arrive at the following existence criteria for RED:OLD on arbitrary graphs:

Theorem 2.9. A graph,

G

, has RED:OLD if and only if

δ (G) \geq 2

and for each distinct

u, v \in V (G)

| N (u) △ N (v) | \geq 2

These existence criteria can be simplified when discussing regular graphs:

Theorem 2.10. [20] Let

G

be an

r

-regular graph with

r \geq 2

. There exists a RED:OLD set for

G

if and only if there exists an OLD set for

G

Further, we have the following results from Seo [20] when discussing cubic graphs specifically:

Theorem 2.11. [20] Let

G

be a cubic graph. If

G

C_{4}

-free, then

V (G)

is a RED:OLD set.

Theorem 2.12. [20] Let

G

be a cubic graph of order

n

. Then we have

\frac{2}{3} n \leq RED:OLD (G) \leq n .

Seo [20] has also constructed an infinite family of finite cubic graphs exhibiting the extremal value of $RED:OLD (G) = \frac{2}{3} n$ .

DET:OLD sets

Similar to the existence criteria for OLD and RED:OLD sets, one can simply use Theorem 1.1 with $S = V (G)$ to arrive at the existence criteria for DET:OLD sets in arbitrary graphs. While there are no simpler existence criteria on arbitrary graphs, the following necessary conditions have been found:

Observation 2.13. [13] If

G

permits DET:OLD, then every

v \in V (G)

has at most one degree 2 neighbor.

Theorem 2.14. [13] If

G_{n, m}

has DET:OLD, then

m \geq ⌈ \frac{3 n - ⌊ \frac{n}{2} ⌋}{2} ⌉

Further, we have the following results from Seo [20] when discussing cubic graphs specifically:

Theorem 2.15. [20] If

G

is a

C_{4}

-free cubic graph, then for any vertex

x \in V (G)

V (G) - {x}

is a DET:OLD set for

G

Theorem 2.16. [20] A cubic graph permits DET:OLD if and only if it is

C_{4}

-free.

Theorem 2.17. [13,20] If

G

is a

C_{4}

-free cubic graph, then

\frac{6}{7} \leq DET:OLD\% (G) \leq \frac{30}{31}

The lower bound from Theorem 2.17 is achieved by the infinite hexagonal grid [23] and an infinite family of finite cubic graphs [20].

ERR:OLD Sets

Because an ERR:OLD set requires 3-domination, many graphs do not allow an ERR:OLD set to exist. In light of this, our next theorem characterizes all graphs that permit an ERR:OLD set.

Theorem 2.18. A graph

G

permits an ERR:OLD set if and only if

δ (G) \geq 3

and for every

C_{4}

subgraph,

a b c d

| N (a) △ N (c) | \geq 3

Proof. First, assume to the contrary that there exists a vertex $v$ with $d e g (v) \leq 2$ ; then, $v$ cannot be 3-dominated, a contradiction. Similarly, if we assume there exists $a, c \in V (G)$ with $| N (a) △ N (c) | \leq 2$ , then $a$ and $c$ could not be $3$ -distinguished, a contradiction.

For the converse, suppose $G$ satisfies both properties of the theorem statement. To demonstrate the existence of ERR:OLD, we will conservatively let $S = V (G)$ be the detector set. Clearly, $δ (G) \geq 3$ guarantees all vertices will be 3-dominated, so we need only show that all vertex pairs are $3$ -distinguished. Let $u, v \in V (G)$ with $u \neq v$ . If $d (u, v) \geq 3$ then $u$ and $v$ will have non-intersecting neighborhoods and thus be $3$ -distinguished; otherwise, we can assume $d (u, v) \leq 2$ . Suppose $d (u, v) = 2$ , and let $u x v$ be a path from $u$ to $v$ . If $| N (u) \cap N (v) | = 1$ , then $u$ and $v$ must be 4-distinguished, and we would be done, so assume ${x, y} \subseteq N (u) \cap N (v)$ with $x \neq y$ . Then we have a $C_{4}$ subgraph, $u x v y$ , so by hypothesis $| N (u) △ N (v) | \geq 3$ and $(u, v)$ are $3$ -distinguished. Finally, suppose $d (u, v) = 1$ . If there is some $p \in (N (u) △ N (v)) - {u, v}$ , then $u$ and $v$ will be 3-distinguished by ${u, v, p}$ , and we would be done; otherwise, we assume that $N (u) △ N (v) = {u, v}$ . Because $δ (G) \geq 3$ , it must be that $\exists p, q \in N (u) \cap N (v)$ with $p \neq q$ . Then we have a $C_{4}$ subgraph $u p v q$ , so by hypothesis $u$ and $v$ must be $3$ -distinguished, completing the proof.

From Theorem 2.18, it is clear that checking whether or not a graph permits an ERR:OLD set can be done in polynomial time.

Corollory 2.19. A

C_{4}

-free graph,

G

, permits an ERR:OLD set if and only if

δ (G) \geq 3

Two distinct vertices $u, v \in V (G)$ are said to be twins if $N [u] = N [v]$ (closed twins) or $N (u) = N (v)$ (open twins). From Theorem 2.18, we see that if $G$ has twins $u$ and $v$ , then it cannot have an ERR:OLD set since $d e g (u) = d e g (v) \leq 2$ or $u$ and $v$ form the corners of a $C_{4}$ subgraph with $| N (u) △ N (v) | \leq 2$ .

Corollary 2.20. If

G

permits an ERR:OLD set, then

G

is twin-free.

Next, we will show that there are no graphs with ERR:OLD sets on $n \leq 6$ vertices.

Theorem 2.21. If

G

has an ERR:OLD set, then

n \geq 7

Proof. Firstly, we know that $G$ cannot be acyclic because an ERR:OLD set requires $δ (G) \geq 3$ . Thus, $G$ has a cycle, which we will exploit in casing. We will proceed by casing on the size of the smallest cycle, which implies that edges cannot be added between the vertices of said smallest cycle. We assume $n \leq 6$ , as otherwise we would be done. If the smallest cycle is $C_{k}$ for $5 \leq k \leq 6$ , then every vertex in the cycle must have a third dominator, and these additional $k$ vertices must all be distinct to avoid creating smaller cycles; thus $n \geq 2 k \geq 10 > 6$ , a contradiction. Suppose the smallest cycle is a $C_{4}$ subgraph $a b c d$ , then each vertex in the cycle must have a third dominator, $a^{'}$ , $b^{'}$ , $c^{'}$ , and $d^{'}$ adjacent to $a$ , $b$ , $c$ , and $d$ , respectively. We see that $a^{'} \neq b^{'} \neq c^{'} \neq d^{'} \neq a^{'}$ ; however, because $n \leq 6$ it must be that $a^{'} = c^{'}$ and $b^{'} = d^{'}$ . We see that $a$ and $c$ cannot have any additional edges without creating a smaller cycle, but they are open twins and so cannot be $3$ -distinguished, a contradiction. Thus, we can assume that $G$ has a triangle.

Next, suppose there exists a 4-Cycle $a b c d$ with $b d \in E (G)$ , which we call a “diamond” subgraph. If $a c \notin E (G)$ then distinguishing $a$ and $c$ will result in $n \geq 7$ , a contradiction; thus, we can assume that $a c \in E (G)$ , meaning we have a $K_{4}$ subgraph. By symmetry, we can assume that $a$ , $b$ , and $c$ have third dominators $a^{'}$ , $b^{'}$ , and $c^{'}$ . If $a^{'}$ , $b^{'}$ , and $c^{'}$ are all distinct, then $n \geq 7$ and we would be done; otherwise without loss of generality assume $a^{'} = b^{'}$ . Suppose $a^{'} = b^{'} = c^{'}$ ; then we require $d a^{'} \in E (G)$ to be able to distinguish $d$ and $a^{'}$ , and by symmetry we have $\exists x \in N (d) - N (a^{'}) - {a, b, c, d, a^{'}}$ . We now have a $K_{5}$ subgraph plus an extra vertex $x \in N (d)$ . Distinguishing $a$ and $b$ requires without loss of generality $x \in N (a)$ , but then $a$ and $d$ cannot be $3$ -distinguished, a contradiction. Otherwise, we can assume $a^{'} = b^{'} \neq c^{'}$ ; we see that distinguishing $a$ and $b$ requires, without loss of generality, $b c^{'} \in E (G)$ . If $a^{'} d \in E (G)$ then $d c^{'} \in E (G)$ to distinguish $a$ and $d$ ; however, $b$ and $d$ can no longer be $3$ -distinguished, a contradiction, so we assume $a^{'} d \notin E (G)$ and $d c^{'} \notin E (G)$ . If $a^{'} c \in E (G)$ then $b$ and $c$ cannot be $3$ -distinguished, a contradiction, so by symmetry we assume $a^{'} c \notin E (G)$ and $c^{'} a \notin E (G)$ . Thus, 3-dominating $a^{'}$ and $c^{'}$ requires $a^{'} c^{'} \in E (G)$ , but then $c$ and $a^{'}$ cannot be $3$ -distinguished, a contradiction. Thus, the existence of a diamond subgraph implies that $n \geq 7$ .

At this point, we know that $G$ has a triangle, say $a b c$ . To 3-dominate the vertices in $a b c$ , assume $\exists a^{'} \in N (a) - {b, c}$ , $\exists b^{'} \in N (b) = {a, c}$ , and $c^{'} \in N (c) - {a, b}$ . Additionally, we can assume $a^{'}$ , $b^{'}$ , and $c^{'}$ are distinct because otherwise we produce a diamond subgraph. To 3-dominate $a^{'}$ , $b^{'}$ , and $c^{'}$ without producing a diamond subgraph, it must be that ${a^{'} b^{'}, b^{'} c^{'}, c^{'} a^{'}} \subseteq E (G)$ . At this point we can no longer add any edges without producing a diamond subgraph, but $a^{'}$ and $b$ are not $3$ -distinguished, a contradiction, completing the proof.

Figure 2 shows the first graphs with an ERR:OLD set in the lexicographic ordering of $(n, m)$ tuples; i.e., the graphs with the smallest number of edges given the smallest number of vertices. For ERR:OLD, this is $n = 7$ and $m = 12$ .

f2-1 — Figure 2 The two smallest graphs supporting ERR:OLD, which have $n = 7$ and $m = 12$

Next, we will show the relation between the existence of ERR:OLD sets and DET:OLD sets for regular graphs.

Observation 2.22. If

A

and

B

are sets with

| A | = | B |

, then

| A - B | = k

implies

| A △ B | = 2 k

Proof. Suppose $| A - B | = k$ . Then $| A \cap B | = | A | - k = | B | - k$ . Therefore $| A △ B | = | A - B | + | B - A | = k + (| B | - | B \cap A |) = k + (| B | - (| B | - k)) = k + k$ , completing the proof.

Suppose $G$ is a regular graph with DET:OLD. We can conservatively let $S = V (G)$ be the set of detectors. Then every vertex pair in $G$ must be $2^{#}$ -distinguished; thus, Theorem 2.22 yields that every vertex pair is $4$ -distinguished, which is sufficient for the distinguishing requirement of ERR:OLD.

Proposition 2.23. A regular graph

G

with

δ (G) = Δ (G) \geq 3

has a DET:OLD set if and only if it has an ERR:OLD set.

A graph is cubic or 3-regular if every vertex is of degree 3. Jean and Seo [13] have previously proven that a cubic graph has a DET:OLD set if and only if the graph is $C_{4}$ -free; thus, we have the following existence criteria.

Corollary 2.24. A cubic graph

G

has an ERR:OLD set if and only if

G

C_{4}

-free.

Now we consider extremal graphs with $ERR:OLD (G) = n$ with least $m$ . If a graph $G$ has an ERR:OLD set, then Theorem 2.18 yields that $δ (G) \geq 3$ , which serves as a lower bound for the least $m$ , namely $m \geq \frac{3 n}{2}$ . Figures 2 and 3 show extremal graphs with $ERR:OLD (G) = n$ with the fewest number of edges when $7 \leq n \leq 9$ . For even $n \geq 10$ , we will show that cubic graphs exist which meet the theoretical lower bound of $m = \frac{3 n}{2}$ . For odd $n \geq 11$ , this bound of $m = \frac{3 n}{2}$ is trivially unobtainable, but we introduce a new class of “almost-cubic” graphs meeting the lower bound of $m = \frac{3 n + 1}{2}$ . In either case, we provide an extremal graph for each $n \geq 10$ .

f3-1 — Figure 3 Extremal graphs with $ERR:OLD (G) = n$ with the fewest number of edges when $n = 8$ and $n = 9$ .

Definition 2.25.

G

is quasi-cubic if every vertex is degree 3 aside from one degree-4 vertex.

When $n \geq 10$ , cubic and quasi-cubic graphs together form the entire family of extremal graphs with $ERR:OLD (G) = n$ which have the minimum number of edges for a given $n$ . If $S$ is an ERR:OLD set, we know that $v \in S$ if $\exists w \in N (v)$ with $d e g (w) = 3$ . Because every vertex in a cubic or quasi-cubic graph is adjacent to a degree-3 vertex, these classes or graphs require $RED:OLD (G) = n$ if they permit ERR:OLD.

Theorem 2.26. If

G

is cubic or quasi-cubic, then

G

has an ERR:OLD set if and only if

G

C_{4}

-free.

Proof. Suppose $G$ has a $C_{4}$ subgraph, $a b c d$ . Because $G$ is cubic or quasi-cubic, at most one vertex in $a b c d$ can be degree 4, and all others will be degree 3. By symmetry, assume $d e g (a) = d e g (c) = 3$ . Then $a$ and $c$ cannot be 3-distinguished, implying $G$ does not have ERR:OLD.

For the converse, suppose $G$ does not have ERR:OLD. Because $δ (G) \geq 3$ , we know that an ERR:OLD set not existing implies $\exists u, v \in V (G)$ where $u$ and $v$ are not 3-distinguished. Regardless of whether or not $u v \in E (G)$ , we see the only way to have $u$ and $v$ not be 3-distinguished is by having $| N (u) \cap N (v) | \geq 2$ , which creates a $C_{4}$ subgraph, completing the proof.

Suppose we have a cubic graph $G$ that permits an ERR:OLD set. Then, we can construct a quasi-cubic graph from $G$ as shown in the next theorem.

Theorem 2.27. Let

G

be a cubic graph with ERR:OLD where

a, b, c, d \in V (G)

and

a b, c d \in E (G)

such that

a b

and

c d

are not part of a triangle or the terminal edges of a

P_{5}

subgraph. Construct quasi-cubic graph

G^{'}

from

G

by deleting edges

a b

and

c d

and adding a new vertex

x

with

N (x) = {a, b, c, d}

. Then

G^{'}

has an ERR:OLD set.

Proof. By Theorem 2.26, we know that $G$ is $C_{4}$ -free and we need only show that $G^{'}$ is likewise $C_{4}$ -free. Suppose for a contradiction that $G^{'}$ has a $C_{4}$ subgraph; then due to $G$ being $C_{4}$ -free, the $C_{4}$ subgraph must involve vertex $x$ , which is an endpoint of every new edge in $G^{'}$ . By symmetry, we can reduce the problem to two possible cases: the $C_{4}$ includes edges ${a x, x b}$ or edges ${a x, x c}$ , and we will consider $y \in V (G)$ to be the opposite vertex of $x$ in the $C_{4}$ subgraph. If we are in the ${a x, x b}$ case, we see that any choice of $y$ results in $a b y$ forming a triangle in $G$ , a contradiction. Otherwise, in the ${a x, x c}$ case we see that $y \neq b$ and $y \neq d$ because $a b, c d \notin E (G^{'})$ , so $y$ causes $a b$ and $c d$ to be the ends of a $P_{5}$ subgraph in $G$ , a contradiction, completing the proof.

3. NP-Completeness of ERR:OLD minimization

It has been shown that determining many graphical parameters related to detection systems, such as the minimum cardinality of an IC, LD, or OLD set, are NP-complete problems on arbitrary graphs [1,3,4,21]. Similarly, the problems involving RED:OLD and DET:OLD parameters have been known to be NP-complete [5,13]. We will now prove that the problem of determining the smallest ERR:OLD set is also NP-complete. For additional information about NP-completeness, see Garey and Johnson [8].

3-SAT

INSTANCE: Let $X$ be a set of $N$ variables. Let $ψ$ be a conjunction of $M$ clauses, where each clause is a disjunction of three literals from distinct variables of $X$ .
QUESTION: Is there is an assignment of values to $X$ such that $ψ$ is true?

ERR:OLD Minimization

INSTANCE: A graph $G$ and integer $K$ with $7 \leq K \leq | V (G) |$ .
QUESTION: Is there an ERR:OLD set $S$ with $| S | \leq K$ ? Or equivalently, is ERR:OLD( $G$ ) $\leq K$ ?

Lemma 3.1. Given a graph

G

, let

G_{7}

be the subgraph shown in Figure 4, where vertices

{b, c, d, e}

have no additional edges in the larger graph but

{a, f, g}

are permitted to have additional edges to vertices outside of this subgraph. If

S

is an ERR:OLD set for

G

, then

V (G_{7}) \subseteq S

Proof. To 3-distinguish $b$ and $c$ , we require ${b, c, d} \subseteq S$ . To 3-dominate $b$ , we additionally require ${a, f} \subseteq S$ . By symmetry, we have that $V (G_{7}) \subseteq S$ , completing the proof.

f5-1 — Figure 5 Variable ( $F_{i}$ ) and clause ( $H_{j}$ ) graphs

f6-1 — Figure 6 Construction of $G$ from $(\bar{x_{1}} \lor \bar{x_{2}} \lor x_{3}) \land (x_{1} \lor x_{2} \lor \bar{x_{4}}) \land (x_{1} \lor \bar{x_{3}} \lor x_{4})$ with $N = 4$ , $M = 3$ , $K = 109$

Theorem 3.2. The ERR:OLD Minimization problem is NP-complete.

Proof. Clearly, the ERR:OLD minimization is NP, as every possible candidate solution can be generated nondeterministically in polynomial time (specifically, $O (n)$ time), and each candidate can be verified in polynomial time using Theorem 1.1 (iv). To complete the proof, we will now show a reduction from 3-SAT to ERR:OLD minimization.

Let $ψ$ be an instance of the 3-SAT problem with $M$ clauses on $N$ variables. We will construct a graph, $G$ , as follows. For each variable $x_{i}$ , create an instance of the $F_{i}$ graph (Figure 5); this includes a vertex for $x_{i}$ and its negation $\bar{x_{i}}$ . For each clause $y_{j}$ of $ψ$ , create a new instance of the $H_{j}$ graph (Figure 5). For each clause $y_{j} = α \lor β \lor γ$ , create an edge from the $y_{j}$ vertex to $α$ , $β$ , and $γ$ from the variable graphs, each of which is either some $x_{i}$ or $\bar{x_{i}}$ ; for an example, see Figure 6. The resulting graph has precisely $25 N + 8 M$ vertices and $51 N + 17 M$ edges, and can be constructed in polynomial time. To complete the problem instance, we define $K = 22 N + 7 M$ .

Suppose $S \subseteq V (G)$ is an ERR:OLD set on $G$ with $| S | \leq K$ . By Lemma 3.1, we require at least all of the $21 N + 7 M$ detectors shown by the shaded vertices in Figure 5. Additionally, in each $F_{i}$ the vertices $p_{i}$ and $q_{i}$ require $x_{i} \in S$ or $\bar{x_{i}} \in S$ in order to be 3-dominated. Thus, we find that $| S | \geq 22 N + 7 M = K$ , implying that $| S | = K$ , so $| {x_{i}, \bar{x_{i}}} \cap S | = 1$ for each $i \in {1, \dots, N}$ . For each $H_{j}$ , we see that $y_{j}$ is not 3-dominated unless it is adjacent to at least one additional detector from its three neighbors in the $F_{i}$ graphs; therefore, $ψ$ is satisfiable.

For the converse, suppose we have a solution to the 3-SAT problem $ψ$ ; we will show that there is a ERR:OLD, $S$ , on $G$ with $| S | \leq K$ . We construct $S$ by first including all of the $21 N + 7 M$ vertices as shown in Figure 5. Next, for each variable, $x_{i}$ , if $x_{i}$ is true then we let the vertex $x_{i} \in S$ ; otherwise, we let $\bar{x_{i}} \in S$ . Thus, the fully-constructed $S$ has $| S | = 22 N + 7 M = K$ . It can be shown that every vertex pair is now 3-distinguished, and that every vertex which is not a $y_{j}$ clause vertex is 3-dominated. Because we selected each $x_{i} \in S$ or $\bar{x_{i}} \in S$ based on a satisfying truth assignment for $ψ$ , each $y_{j}$ must be adjacent to at least one additional detector vertex from the $F_{i}$ graphs. Thus, all vertices are 3-dominated, implying $S$ is an ERR:OLD set for $G$ with $| S | \leq K$ , completing the proof.

4. ERR:OLD on infinite grids

In this section we will explore constructions of minimum-sized ERR:OLD sets on three popular infinite grids explored in literature: the infinite square grid (SQR), the infinite triangular grid (TRI), and the infinite king grid (KNG). Given this goal, a natural question is how we are to define such a “minimum-sized” infinite subset of an infinite vertex set. For this, we employ the concept of the density of a set of vertices and employ notations such as $ERR:OLD\% (G)$ to denote the minimum density of an ERR:OLD set on $G$ , rather than the cardinality [23]. Formally, where $B_{r} (v) = {u \in V (G) : d (u, v) \leq r}$ , a subset $S \subseteq V (G)$ on a locally-finite (i.e. $B_{r} (v)$ finite for any finite $r$ ) (connected) graph $G$ has density $\underset{r \to \infty}{lim sup} \frac{| B_{r} (v) \cap S |}{| B_{r} (v) |}$ for any $v \in V (G)$ . Notably, the choice of center vertex $v$ can affect the result of this calculation, in which case the density of the graph as a whole is not well-defined in practice. However, it has been proven that any graph satisfying the “slow-growth” property, $lim_{r \to \infty} \frac{| B_{r + 1} (v) |}{| B_{r} (v) |} = 1$ for some $v \in V (G)$ , have the additional property that the density is invariant of the choice of center point [18].

Figure 7 shows an ERR:OLD set with the minimum density we have found so far for the three infinite grids. One can verify that each of these ERR:OLD sets satisfies the domination and distinguishing requirements in Theorem 1.1. Figure 7 (a) shows an ERR:OLD set with a tiling of SQR where seven out of eight vertices are detectors, so $ERR:OLD\% (S Q R) \leq \frac{7}{8}$ . Similarly, we obtain $ERR:OLD\% (T R I) \leq \frac{4}{7}$ and $ERR:OLD\% (K N G) \leq \frac{4}{9}$ from Figure 7 (b) and (c), respectively.

f7-1 — Figure 7 Our best constructions of ERR:OLD sets on SQR (a), TRI (b), and KNG (c).

To establish lower bound densities for domination-based parameters in infinite graphs, we employ a concept termed a share argument, originally introduced by Slater [26] and extensively utilized by other literature [14,19]. Essentially, this technique inverts the problem: instead of directly seeking a lower bound for the density of an ERR:OLD set, we determine an upper bound on the average share of a detector vertex $v \in S$ , denoted $s h (v) = \sum_{u \in N (v)} \frac{1}{d o m (u)}$ , representing its total contribution to the domination of its neighbors. Because $S$ is an open-dominating set, every vertex is 1-open-dominated, and each vertex with $d o m (u) = k$ contributes precisely $\frac{1}{k}$ to the share of each of its $k$ dominators, for a total of $1$ per vertex in $V (G)$ . Therefore, an upper bound for the inverse average share of all detectors forms a lower bound for the density of $S$ in $V (G)$ .

As an example of how share could be used to produce a lower bound for ERR:OLD, suppose $G$ is $k$ -regular and let $v \in S$ be an arbitrary detector vertex in an ERR:OLD set $S \subseteq V (G)$ . We know that $v$ has $k$ neighbors and each neighbor must be 3-dominated due to $S$ being an ERR:OLD set. Therefore, $s h (v) \leq \frac{1}{3} + \frac{1}{3} + \dots + \frac{1}{3} + \frac{1}{3} = \frac{k}{3}$ . Because $v$ was selected arbitrarily, this value of $\frac{k}{3}$ serves as an upper bound for the average share of all detectors, and so its inverse, $\frac{3}{k}$ , represents a lower bound for the minimum density of an ERR:OLD in $G$ . Applying this finding to the infinite grids we will cover, we have the following naive lower bounds: $ERR:OLD\% (S Q R) \geq \frac{3}{4}$ , $ERR:OLD\% (T R I) \geq \frac{1}{2}$ , and $ERR:OLD\% (K N G) \geq \frac{3}{8}$ .

In what follows, we will augment these same naive share arguments with a few additional pieces of information in order to arrive at much higher lower bounds. As a shorthand, we will let $σ_{A}$ denote $\sum_{k \in A} \frac{1}{k}$ for some sequence of single-character symbols, $A$ . Thus, $σ_{a} = \frac{1}{a}$ , $σ_{a b} = \frac{1}{a} + \frac{1}{b}$ , and so on.

f8-1 — Figure 8 SQR labeling scheme. Vertices $v_{1}, v_{2}, \dots, v_{12}$ are labeled as $1, 2, \dots, 12$

Theorem 4.1. The infinite square grid, SQR, has

ERR:OLD % (SQR) \geq \frac{6}{7}

Proof. Let $S$ be an ERR:OLD set on SQR and let $x \in S$ be an arbitrary detector; we will use the labeling scheme shown in Figure 8. We see that in order to distinguish vertices $v_{1}$ and $v_{2}$ we require $| {v_{5}, v_{7}, v_{8}, v_{12}} | \geq 3$ . By symmetry, we also find that for any $A \in {{v_{8}, v_{9}, v_{11}, v_{12}}, {v_{5}, v_{6}, v_{10}, v_{11}}, {v_{6}, v_{7}, v_{9}, v_{10}}}$ , $| A \cap S | \geq 3$ . Suppose $v_{6} \notin S$ ; then we require ${v_{5}, v_{7}, v_{9}, v_{10}, v_{11}} \subseteq S$ due to overlapping $A$ -sets, as well as ${v_{8}, v_{12}} \subseteq S$ to 3-dominate $v_{1}$ and $v_{2}$ . Then $s h (x) \leq σ_{3344} = \frac{7}{6}$ and we would be done; otherwise, we can assume that $v_{6} \in S$ and by symmetry ${v_{8}, v_{10}, v_{12}} \subseteq S$ as well. Suppose $v_{5} \notin S$ ; then we also require ${v_{7}, v_{11}} \subseteq S$ due to overlapping $A$ -sets. Then $s h (x) \leq σ_{3344} = \frac{7}{6}$ and we would be done; otherwise, we can assume that $v_{5} \in S$ and by symmetry ${v_{7}, v_{9}, v_{11}} \subseteq S$ as well. Then $s h (x) \leq σ_{4444} < \frac{7}{6}$ , completing the proof.

f9-1 — Figure 9 TRI labeling scheme. Vertices $v_{1}, v_{2}, \dots, v_{18}$ are labeled as $1, 2, \dots, 18$

Theorem 4.2. The infinite triangular grid, TRI, has

ERR:OLD % (TRI) \geq \frac{6}{11}

Proof. Let $S$ be an ERR:OLD set on TRI and let $x \in S$ be an arbitrary detector; we will use the labeling scheme shown in Figure 9. We know that every vertex must be 3-dominated; suppose ${v_{1}, v_{3}, v_{5}}$ are all exactly 3-dominated. If $v_{2} \in S$ , then we see that $v_{1}$ and $v_{3}$ (which are exactly 3-dominated) cannot be $3$ -distinguished, a contradiction; otherwise we can assume that $v_{2} \notin S$ and by symmetry $v_{4}, v_{6} \notin S$ as well. Then to 3-dominated $x$ , we require ${v_{1}, v_{3}, v_{5}} \subseteq S$ . If at least two vertices in ${v_{2}, v_{4}, v_{6}}$ are 4-dominated, then $s h (x) \leq σ_{344333} = \frac{11}{6}$ and we would be done; otherwise, without loss of generality assume that $d o m (v_{2}) = d o m (v_{4}) = 3$ . We see that $v_{6}$ is already adjacent to three detectors, implying $v_{7} \notin S$ , and by symmetry $v_{9} \notin S$ as well. Then $v_{1}$ cannot be 3-dominated, a contradiction. Otherwise, we know that there must be at least one 4-dominated vertex in ${v_{1}, v_{3}, v_{5}}$ , and symmetry yields a second 4-dominated vertex in ${v_{2}, v_{4}, v_{6}}$ , giving $s h (x) \leq σ_{443333} = \frac{11}{6}$ and completing the proof.

f10-2 — Figure 10 KNG labeling scheme. Vertices $v_{1}, v_{2}, \dots, v_{24}$ are labeled as $1, 2, \dots, 24$

f11-1 — Figure 11 The four non-isomorphic valid configurations to distribute three 4-dominated vertices in $N(x)$. Red and blue vertices represent 3- and 4-dominated vertices, respectively

Theorem 4.3. The infinite king grid, KNG, has

ERR:OLD % (KNG) \geq \frac{5}{12}

Proof. Let

S

be an ERR:OLD set on KNG and let

x \in S

be an arbitrary detector; we will use the labeling scheme shown in Figure 10. To begin, suppose that each vertex

v \in {v_{1}, v_{2}, v_{3}}

has

d o m (v) = 3

. We see that

| N_{S} (v_{1}) \cap N_{S} (v_{2}) | \geq 1

due to

x

; if this intersect reaches size 2, then

v_{1}

and

v_{2}

will not be able to be

3

-distinguished. Thus, we can assume that

((N (v_{1}) \cap N (v_{2})) - {x}) \cap S = \emptyset

; that is,

{v_{3}, v_{9}, v_{10}} \cap S = \emptyset

, and by symmetry

{v_{1}, v_{12}, v_{13}} \cap S = \emptyset

as well. We see that

v_{2}

cannot be 3-dominated, a contradiction; therefore, we can assume that at least one vertex in

{v_{1}, v_{2}, v_{3}}

is 4-dominated, and by symmetry we also have that for any

A \in {{v_{3}, v_{4}, v_{5}}, {v_{5}, v_{6}, v_{7}}, {v_{7}, v_{8}, v_{1}}}

, there is at least one vertex in

A

which is 4-dominated.

In order to simultaneously satisfy all four $A$ -sets (“corners”), we require at least two vertices which are 4-dominated. There exists only one non-isomorphic configuration with the minimum of two such vertices, so without loss of generality let $d o m (v_{1}) \geq 4$ and $d o m (v_{5}) \geq 4$ with all other vertices in $N (x)$ being (exactly) 3-dominated. Similar to before, we see that $x \in N_{S} (v_{2}) \cap N_{S} (v_{3})$ , implying that ${v_{1}, v_{12}, v_{13}} \cap S = \emptyset$ and by symmetry ${v_{5}, v_{14}, v_{20}, v_{21}, v_{22}} \cap S = \emptyset$ as well. Applying the same reasoning to $v_{2}$ and $v_{4}$ gives us $v_{3} \notin S$ , and by symmetry $v_{7} \notin S$ as well. Applying this again to $v_{2}$ and $v_{8}$ gives $v_{9} \notin S$ , and by symmetry $v_{17} \notin S$ . To 3-dominate each vertex in ${v_{2}, v_{3}, v_{4}, v_{6}, v_{7}, v_{8}}$ , we require ${v_{2}, v_{4}, v_{6}, v_{8}, v_{10}, v_{11}, v_{15}, v_{16}, v_{18}, v_{19}, v_{23}, v_{24}} \subseteq S$ . We see that $d o m (v_{1}) = d o m (v_{5}) = 5$ , so $s h (x) = σ_{55333333} = \frac{12}{5}$ and we would be done. Otherwise, we know that there must be at least three vertices in $N (x)$ which are 4-dominated. If $N (x)$ has at least four vertices which are 4-dominated, then $s h (x) \leq σ_{44443333} < \frac{12}{5}$ and we would be done; otherwise, we may assume there are precisely three such vertices. Additionally, if any of these three vertices is 5-dominated, then $s h (x) \leq σ_{54433333} < \frac{12}{5}$ and we would be done; otherwise, we may assume $N (x)$ contains exactly three vertices which are exactly 4-dominated, and all other vertices in $N (x)$ are exactly 3-dominated. There are four non-isomorphic configurations which satisfy these constraints, as shown in Figure 11. We will now show that each of these cases has $s h (x) \leq \frac{12}{5}$ .

Case 1: Suppose $d o m (v_{1}) = d o m (v_{4}) = d o m (v_{6}) = 4$ and all other vertices in $N (x)$ are exactly 3-dominated. We first see that $x \in N (v_{3}) \cap N (v_{7})$ , implying that ${v_{1}, v_{5}} \cap S = \emptyset$ . Applying this same logic to $v_{2}$ and $v_{5}$ gives us $v_{3} \notin S$ , and by symmetry $v_{7} \notin S$ as well. Applying this to $v_{3}$ and $v_{5}$ gives us $v_{4} \notin S$ , and $v_{6} \notin S$ by symmetry. We see that $x$ cannot be 3-dominated, a contradiction, completing this case.

Case 2: Suppose $d o m (v_{3}) = d o m (v_{5}) = d o m (v_{7}) = 4$ and all other vertices in $N (x)$ are exactly 3-dominated. Applying similar logic as before, from $v_{1}$ and $v_{2}$ , we see that ${v_{3}, v_{9}, v_{10}} \cap S = \emptyset$ , and by symmetry ${v_{7}, v_{24}} \cap S = \emptyset$ as well. Applying this to $v_{2}$ and $v_{4}$ gives us $v_{13} \notin S$ , and $v_{21} \notin S$ by symmetry. Next, applying this to $v_{4}$ and $v_{6}$ gives us ${v_{5}, v_{17}} \cap S = \emptyset$ . Finally, applying this to $v_{2}$ and $v_{8}$ gives us $v_{1} \notin S$ . To 3-dominated each vertex in ${v_{1}, v_{2}, v_{8}}$ , we require ${v_{2}, v_{8}, v_{11}, v_{12}, v_{22}, v_{23}} \subseteq S$ . To distinguish $v_{1}$ and $x$ , we require ${v_{4}, v_{6}} \subseteq S$ . Because $v_{3}$ is now 4-dominated, it must be that $v_{14} \notin S$ , and $v_{20} \notin S$ by symmetry. Then to 3-dominate $v_{4}$ and $v_{6}$ we require ${v_{15}, v_{16}, v_{18}, v_{19}} \subseteq S$ . However, this causes $v_{5}$ to be 5-dominated, a contradiction, completing this case.

Case 3: Suppose $d o m (v_{2}) = d o m (v_{5}) = d o m (v_{7}) = 4$ and all other vertices in $N (x)$ are exactly 3-dominated. Applying the usual reasoning to $v_{3}$ and $v_{4}$ yields ${v_{5}, v_{13}, v_{14}} \cap S = \emptyset$ , and by symmetry ${v_{7}, v_{9}, v_{24}} \cap S = \emptyset$ as well. Applying this again to $v_{4}$ and $v_{6}$ gives $v_{17} \notin S$ , and by symmetry $v_{21} \notin S$ as well. With $v_{1}$ and $v_{4}$ , we have $v_{3} \notin S$ , and by symmetry $v_{1} \notin S$ as well. With $v_{1}$ and $v_{3}$ , we have $v_{2} \notin S$ . To dominate each vertex in ${v_{1}, v_{2}, v_{3}, v_{4}, v_{8}}$ , we require ${v_{4}, v_{8}, v_{10}, v_{11}, v_{12}, v_{15}, v_{16}, v_{22}, v_{23}} \subseteq S$ . To 3-dominate $x$ , we require $v_{6} \in S$ . Then $v_{5}$ and $v_{7}$ become 4-dominated, implying $v_{18}, v_{20} \notin S$ , contradicting $d o m (v_{6}) = 3$ and completing this case.

Case 4: Suppose $d o m (v_{1}) = d o m (v_{2}) = d o m (v_{5}) = 4$ and all other vertices in $N (x)$ are exactly 3-dominated. Applying the usual logic to $v_{3}$ and $v_{4}$ yields ${v_{5}, v_{13}, v_{14}} \cap S = \emptyset$ . Applying this to $v_{6}$ and $v_{7}$ yields ${v_{20}, v_{21}} \cap S = \emptyset$ . Vertices $v_{7}$ and $v_{8}$ yield ${v_{1}, v_{22}} \cap S = \emptyset$ . Vertices $v_{6}$ and $v_{8}$ yield $v_{7} \notin S$ , and vertices $v_{4}$ and $v_{6}$ yield $v_{17} \notin S$ . To 3-dominate $v_{6}$ and $v_{7}$ , we require ${v_{6}, v_{8}, v_{18}, v_{19}} \subseteq S$ . If $v_{4} \in S$ , then $v_{5}$ would become 4-dominated, implying $v_{3}, v_{16} \notin S$ , contradicting that $v_{4}$ is 3-dominated; otherwise, we may assume that $v_{4} \notin S$ . To distinguish $v_{7}$ and $x$ , we require $v_{2}, v_{3} \in S$ . We see that $v_{1}$ is 4-dominated, implying that ${v_{9}, v_{10}, v_{24}} \cap S = \emptyset$ . Finally, we find that $v_{8}$ cannot be 3-dominated, a contradiction, completing the proof.

The following theorem summarizes bounds for minimum ERR:OLD set densities in three infinite grids: the infinite square grid (SQR), the infinite triangular grid (TRI), and the infinite king grid (KNG).

Theorem 4.4. The following are upper and lower bounds for

ERR:OLD\% (G)

on several infinite grids:

(i) For SQR, $\frac{6}{7} \leq ERR:OLD\% (S Q R) \leq \frac{7}{8}$ .

(ii) For TRI, $\frac{6}{11} \leq ERR:OLD\% (T R I) \leq \frac{4}{7}$ .

(iii) For KNG, $\frac{5}{12} \leq ERR:OLD\% (K N G) \leq \frac{4}{9}$ .

Table 1 concludes this section with the upper and lower bounds for other fault-tolerant OLD sets on four of the most studied infinite grids including the infinite hexagonal grid (HEX). Note that $ERR:OLD\% (HEX) = 1$ because HEX is cubic, which requires every vertex to be a detector.

Table 1 Minimum densities for Fault-tolerant OLD sets in the four infinite grids
parameter	hexagonal	square	triangular	king
OLD [17,19,21]	$\frac{1}{2}$	$\frac{2}{5}$	$\frac{4}{13}$	$[\frac{6}{25}, \frac{1}{4}]$
RED:OLD [15,23]	$\frac{2}{3}$	$\frac{1}{2}$	$\frac{3}{8}$	$[\frac{3}{10}, \frac{1}{3}]$
DET:OLD [14,23]	$\frac{6}{7}$	$\frac{3}{4}$	$\frac{1}{2}$	$[\frac{3}{8}, \frac{13}{30}]$
ERR:OLD	$1$	$[\frac{6}{7}, \frac{7}{8}]$	$[\frac{6}{11}, \frac{4}{7}]$	$[\frac{5}{12}, \frac{4}{9}]$

Declarations

The authors declare no conflict of interest.

References:

I. Charon, O. Hudry, and A. Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is np-hard. Theoretical Computer Science, 290:2109–2120, 2003.
M. Chellali, N. J. Rad, S. Seo, and P. Slater. On open neighborhood locating-dominating in graphs. Electronic Journal of Graph Theory and Applications, 2(2):87–98, 2014.
G. Cohen, I. Honkala, A. Lobstein, and G. Zémor. On identifying codes. In Proceedings of DIMACS Workshop on Codes and Association Schemes ’99, volume 56, pages 97–109, Piscataway, USA, 2001.
C. J. Colbourn, P. Slater, and L. K. Stewart. Locating dominating sets in series parallel networks. Congressus Numerantium, 56:135–162, 1987.
R. Dohner and S. Seo. The np-completeness of redundant open-locating-dominating set. CoRR, abs/2201.05252:9 pages, 2022. https://doi.org/10.48550/arXiv.2201.05252.
P. Erdős. Some combinatorial, geometric and set theoretic problems in measure theory. In Measure Theory Oberwolfach 1983, pages 321–327. Springer Berlin Heidelberg, Berlin, Heidelberg, 1984.
F. Foucaud, N. Ghareghani, A. Roshany-tabrizi, and P. Shariani. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics, 302:76–79, 2021. https://doi.org/10.1016/j.dam.2021.06.006.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco, 1979.
R. M. Givens, R. K. Kincaid, W. Mao, and G. Yu. Mixed-weight open locating-dominating sets. In Proceedings of 51st Annual Conference on Information Sciences and Systems (CISS), pages 1–6, 2017. https://doi.org/10.1109/CISS.2017.7926110.
M. Henning and A. Yeo. Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs. Graphs and Combinatorics, 30:909–932, 2014. https://doi.org/10.1007/s00373-013-1311-2.
I. Honkala, T. Laihonen, and S. Ranto. On strongly identifying codes. Discrete Mathematics, 254:191–205, 2002. https://doi.org/10.1016/S0012-365X(01)00357-0.
D. Jean and A. Lobstein. Watching systems, identifying, locating-dominating and discriminating codes in graphs, 2024. Available at: https://dragazo.github.io/bibdom/main.pdf.
D. Jean and S. Seo. On error-detecting open-locating-dominating sets. arXiv, abs/2306.12583, 2023. https://doi.org/10.48550/arXiv.2306.12583.
D. Jean and S. Seo. Optimal error-detecting open-locating-dominating set on the infinite triangular grid. Discussiones Mathematicae Graph Theory, 43(2):445–455, 2023. https://doi.org/10.7151/dmgt.2374.
D. Jean and S. Seo. Fault-tolerant detection systems on the king’s grid. arXiv, abs/2211.14962, 2022. https://doi.org/10.48550/arXiv.2211.14962.
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, IT-44:599–611, 1998.
R. Kincaid, A. Oldham, and G. Yu. Optimal open-locating-dominating sets in infinite triangular grids. Discrete Applied Mathematics, 193:139–144, 2015. https://doi.org/10.1016/j.dam.2015.04.024.
R. Sampaio, G. Sobral, and Y. Wakabayashi. Density of identifying codes of hexagonal grids with finite number of rows. RAIRO-Operations Research, 58(2):1633–1651, 2024. https://doi.org/10.1051/ro/2024046.
S. Seo. Open-locating-dominating sets in the infinite king grid. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:31–47, 2018.
S. Seo. Fault-tolerant detectors for distinguishing sets in cubic graphs. Discrete Applied Mathematics, 293:25–33, 2021. https://doi.org/10.1016/j.dam.2021.01.008.
S. Seo and P. Slater. Open neighborhood locating-dominating sets. Australasian Journal of Combinatorics, 46:109–119, 2010.
S. Seo and P. Slater. Open neighborhood locating-dominating in trees. Discrete Applied Mathematics, 159:484–489, 2011. https://doi.org/10.1016/j.dam.2010.12.010.
S. Seo and P. Slater. Fault tolerant detectors for distinguishing sets in graphs. Discussiones Mathematicae Graph Theory, 35:797–818, 2015. http://dx.doi.org/10.7151/dmgt.1838.
S. Seo and P. Slater. Generalized set dominating and separating systems. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:15–29, 2018.
P. Slater. Domination and location in acyclic graphs. Networks, 7:55–64, 1987.
P. Slater. Fault-tolerant locating-dominating sets. Discrete Mathematics, 249:179–189, 2002.

[1] I. Charon, O. Hudry, and A. Lobstein. Minimizing the size of an identifying or locating-dominating code in a graph is np-hard. Theoretical Computer Science, 290:2109–2120, 2003.

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

[3] G. Cohen, I. Honkala, A. Lobstein, and G. Zémor. On identifying codes. In Proceedings of DIMACS Workshop on Codes and Association Schemes ’99, volume 56, pages 97–109, Piscataway, USA, 2001.

[4] C. J. Colbourn, P. Slater, and L. K. Stewart. Locating dominating sets in series parallel networks. Congressus Numerantium, 56:135–162, 1987.

[5] R. Dohner and S. Seo. The np-completeness of redundant open-locating-dominating set. CoRR, abs/2201.05252:9 pages, 2022. https://doi.org/10.48550/arXiv.2201.05252.

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

[7] F. Foucaud, N. Ghareghani, A. Roshany-tabrizi, and P. Shariani. Characterizing extremal graphs for open neighbourhood location-domination. Discrete Applied Mathematics, 302:76–79, 2021. https://doi.org/10.1016/j.dam.2021.06.006.

[8] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman, San Francisco, 1979.

[9] R. M. Givens, R. K. Kincaid, W. Mao, and G. Yu. Mixed-weight open locating-dominating sets. In Proceedings of 51st Annual Conference on Information Sciences and Systems (CISS), pages 1–6, 2017. https://doi.org/10.1109/CISS.2017.7926110.

[10] M. Henning and A. Yeo. Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs. Graphs and Combinatorics, 30:909–932, 2014. https://doi.org/10.1007/s00373-013-1311-2.

[11] I. Honkala, T. Laihonen, and S. Ranto. On strongly identifying codes. Discrete Mathematics, 254:191–205, 2002. https://doi.org/10.1016/S0012-365X(01)00357-0.

[12] D. Jean and A. Lobstein. Watching systems, identifying, locating-dominating and discriminating codes in graphs, 2024. Available at: https://dragazo.github.io/bibdom/main.pdf.

[13] D. Jean and S. Seo. On error-detecting open-locating-dominating sets. arXiv, abs/2306.12583, 2023. https://doi.org/10.48550/arXiv.2306.12583.

[14] D. Jean and S. Seo. Optimal error-detecting open-locating-dominating set on the infinite triangular grid. Discussiones Mathematicae Graph Theory, 43(2):445–455, 2023. https://doi.org/10.7151/dmgt.2374.

[15] D. Jean and S. Seo. Fault-tolerant detection systems on the king’s grid. arXiv, abs/2211.14962, 2022. https://doi.org/10.48550/arXiv.2211.14962.

[16] 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, IT-44:599–611, 1998.

[17] R. Kincaid, A. Oldham, and G. Yu. Optimal open-locating-dominating sets in infinite triangular grids. Discrete Applied Mathematics, 193:139–144, 2015. https://doi.org/10.1016/j.dam.2015.04.024.

[18] R. Sampaio, G. Sobral, and Y. Wakabayashi. Density of identifying codes of hexagonal grids with finite number of rows. RAIRO-Operations Research, 58(2):1633–1651, 2024. https://doi.org/10.1051/ro/2024046.

[19] S. Seo. Open-locating-dominating sets in the infinite king grid. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:31–47, 2018.

[20] S. Seo. Fault-tolerant detectors for distinguishing sets in cubic graphs. Discrete Applied Mathematics, 293:25–33, 2021. https://doi.org/10.1016/j.dam.2021.01.008.

[21] S. Seo and P. Slater. Open neighborhood locating-dominating sets. Australasian Journal of Combinatorics, 46:109–119, 2010.

[22] S. Seo and P. Slater. Open neighborhood locating-dominating in trees. Discrete Applied Mathematics, 159:484–489, 2011. https://doi.org/10.1016/j.dam.2010.12.010.

[23] S. Seo and P. Slater. Fault tolerant detectors for distinguishing sets in graphs. Discussiones Mathematicae Graph Theory, 35:797–818, 2015. http://dx.doi.org/10.7151/dmgt.1838.

[24] S. Seo and P. Slater. Generalized set dominating and separating systems. Journal of Combinatorial Mathematics and Combinatorial Computing, 104:15–29, 2018.

[25] P. Slater. Domination and location in acyclic graphs. Networks, 7:55–64, 1987.

[26] P. Slater. Fault-tolerant locating-dominating sets. Discrete Mathematics, 249:179–189, 2002.

Contents

Congressus Numerantium

Error-correcting open-locating-dominating sets

Abstract

1. Introduction

2. Existence of ERR:OLD sets and extremal graphs

OLD sets

RED:OLD sets

DET:OLD sets

ERR:OLD Sets

3. NP-Completeness of ERR:OLD minimization

3-SAT

ERR:OLD Minimization

4. ERR:OLD on infinite grids

Declarations

References:

Information

Guidelines

CP Initiatives

Follow CP