Let \(G\) be a graph of a network system with vertices, \(V(G)\), representing physical locations and edges, \(E(G)\), representing informational connectivity. A locating-dominating (LD) set \(S \subseteq V(G)\) is a subset of vertices representing detectors capable of sensing an “intruder” at precisely their location or at some unknown point in their open-neighborhood. An LD set must be capable of locating an intruder anywhere in the graph using this collection of detectors. We explore three types of fault-tolerant LD sets: redundant LD sets, which allow at most one detector to be removed or disabled, error-detecting LD sets, which allow at most one false negative, and error-correcting LD sets, which allow at most one error (false positive or false negative). In particular, we determine lower and upper bounds for the minimum density of these three fault-tolerant locating-dominating sets in the infinite king grid.
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). Suppose \(G\) models some system or facility with vertices representing physical locations or pieces of hardware and edges representing their physical or informational connectivity. There may be some “intruder” or other undesirable event in the system, which must be automatically detected and located anywhere in the graph via detectors placed at some subset \(S \subseteq V(G)\) of vertices.
A detector vertex \(v \in S\) is associated with a set of detection regions, \(R(v) \subseteq \mathscr{P}(V(G))\), representing the areas in which it can sense an intruder. A detection system is a set of detector vertices, \(S \subseteq V(G)\), such that an intruder can be precisely located anywhere in the graph provided the detection signal (presence or absence of an intruder) for every detection region. In this paper, we will explore locating-dominating (LD) sets, which are a class of detection system whose detectors have two detection regions: \(R(v) = \{\{v\}, N(v)\}\), where \(N(v)\) denotes the open-neighborhood of \(v\), \(\{u \in V(G) : uv \in E(G)\}\). Other choices for \(R(v)\) have been explored, such as \(R(v) = \{N(v)\}\), yielding open-locating-dominating (OLD) sets [13,17], or \(R(v) = \{N[v]\}\)—where \(N[v]\) denotes the closed neighborhood of \(v\), \(N(v) \cup \{v\}\), yielding identifying codes (ICs) [12]. Jean and Lobstein [6] maintain a bibliography containing over 500 papers on these topics and related graphical parameters.
Conceptually, every LD detector vertex \(v \in S\) will transmit a value of 0 denoting no intruder, 1 denoting an intruder in the open-neighborhood, or 2 denoting an intruder at \(v\). The goal is then to select a sufficient subset of vertices \(S \subseteq V(G)\) so that we can locate an intruder anywhere in the graph. In this paper, we are interested in going one step further: we would like the system to be able to function even in the event of an error, known as a fault-tolerant LD (FTLD) set. In particular, we consider three types of FTLD sets: redundant LD (RED:LD) sets, in which the system must be fully functioning even if at most one detector is removed or disabled, error-detecting LD (DET:LD) sets, where the system allows at most one false-negative (i.e. sending 0 instead of 1 or 2), and error-correcting LD (ERR:LD) sets, where the system allows any single transmission error (false-positive or false-negative).
The following theorems characterize the conditions for LD, RED:LD, DET:LD, and ERR:LD sets in arbitrary graphs.
Theorem 1.1 ([8]). \(S \subseteq V(G)\) is an LD set if and only if the following are true:
\(\forall v \in V(G)-S\), \(|N(v) \cap S| \ge 1\),
\(\forall v,u \in V(G)-S\) with \(v \neq u\), \(|(N(v) \cap S) \triangle (N(u) \cap S)| \ge 1\).
Theorem 1.2 ([8]). \(S \subseteq V(G)\) is a RED:LD set if and only if the following are true:
\(\forall v \in V(G)\), \(|N[v] \cap S| \ge 2\),
\(\forall v \in S\) and \(\forall u \in V(G)-S\), \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{v\}| \ge 1\),
\(\forall v,u \in V(G)-S\) with \(u \neq v\), \(|(N(v) \cap S) \triangle (N(u) \cap S)| \ge 2\).
Theorem 1.3 ([10]). \(S \subseteq V(G)\) is a DET:LD set if and only if the following are true:
\(\forall v \in V(G)\), \(|N[v] \cap S| \ge 2\),
\(\forall v,u \in S\) with \(u \neq v\), \(|(N(v) \cap S) \triangle (N(u) \cap S)| \ge 1\),
\(\forall v \in V(G)-S\) and \(\forall u \in S\), \(|(N(v) \cap S) – (N(u) \cap S)| \ge 2\) or \(|(N(u) \cap S) – (N(v) \cap S)| \ge 1\),
\(\forall v,u \in V(G)-S\) with \(u \!\neq\! v\), \(\!|(N(v) \cap S) – (N(u) \cap S)| \ge 2\) or \(|(N(u) \cap S) – (N(v) \cap S)| \ge 2\).
Theorem 1.4 ([11]). \(S \subseteq V(G)\) is an ERR:LD set if and only if the following are true:
\(\forall v \in V(G)\), \(|N[v] \cap S| \ge 3\)
\(\forall v,u \in S\) with \(u \neq v\), \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{v, u\}| \ge 1\),
\(\forall v \in V(G)-S\) and \(\forall u \in S\), \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{u\}| \ge 2\),
\(\forall v,u \in V(G)-S\) with \(u \neq v\), \(|(N(v) \cap S) \triangle (N(u) \cap S)| \ge 3\).
For an LD-based detection system, a vertex \(x\) is said to be \(k\)-dominated if \(|N[v] \cap S| \ge k\), and a vertex pair \((v,u)\) is said to be \(k\)-distinguished if \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{v,u\}| \ge k\). When discussing any particular type of detection system with a known characterization, we will also say that a vertex pair is simply “distinguished” if it satisfies said characterization. The properties given in Theorems 1.2 and 1.4 can be rewritten as the following, which make use of \(k\)-domination and \(k\)-distinguishing.
Corollary 1.5 ([8]). \(S \subseteq V(G)\) is a RED:LD set if and only if the following are true:
\(\forall v \in V(G)\), \(|N[v] \cap S| \ge 2\),
\(\forall v,u \in V(G)\) with \(u \neq v\), \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{v, u\}| \ge 2 – |\{v,u\} \cap S|\).
Corollary 1.6 ([11]). \(S \subseteq V(G)\) is an ERR:LD set if and only if the following are true:
\(\forall v \in V(G)\), \(|N[v] \cap S| \ge 3\),
\(\forall v,u \in V(G)\) with \(u \neq v\), \(|((N(v) \cap S) \triangle (N(u) \cap S)) – \{v, u\}| \ge 3 – |\{v,u\} \cap S|\).
Given a graph, \(G\), it is clear that any superset of a detection system on \(G\) is also a detection system on \(G\), as the extra sensor data could simply be discarded. Thus, we are interested in the smallest (optimal) sets with the required properties. Jean and Seo [8,10,11] have studied such optimal sets for special classes of graphs such as trees, cubic graphs, and infinite grids. They also proved that these minimization problems on arbitrary graphs are NP-Complete. In this paper, we consider optimal sets for these three fault-tolerant LD set parameters in the infinite king grid (K), an 8-regular graph inspired by a chess board, with edges denoting the typical eight moves of a king. Specifically, we explore upper and lower bounds for the smallest RED:LD, DET:LD, and ERR:LD sets on \(\textrm{K}\).
The density of a subset \(S \subseteq V(G)\) is the ratio of \(|S|\) to \(|V(G)|\), or more formally, \(\limsup_{r \to \infty} \frac{|B_r(v) \cap S|}{|B_r(v)|}\) for some center point \(v \in V(G)\) where \(B_r(v) = \{u \in V(G) : d(u,v) \le r\}\) is the ball of radius \(r\) about \(v\). In this paper, we will only explore graphs which satisfy the “slow-growth” property [15] of \(\lim_{r \to \infty} \frac{|B_{r+1}(v)|}{|B_r(v)|} = 1\), which guarantees that the density is invariant of the center point \(v\), and that the density of a periodic tiling is equal to the density within any single tile. The notations \(\textrm{RED:LD}(G)\), \(\textrm{DET:LD}(G)\), and \(\textrm{ERR:LD}(G)\) denote the minimum density of such a set on \(G\).
In Section 2, we discuss some of the previous results for optimal (minimum) fault-tolerant variants of LD, OLD, and IC sets. In Section 3, we introduce the concepts of “share arguments” and “discharging techniques,” which are used later in Section 4 to determine bounds for RED:LD, DET:LD, and ERR:LD sets on the infinite king grid.
The concept of LD sets was originally introduced by Slater [19,20]. Slater [21] also explored “FTLD” sets (equivalent to DET:LD sets in this paper), and proved upper and lower bounds for optimal DET:LD sets in the infinite square grid (SQ): \(\left[\frac{12}{23}, \frac{3}{5}\right]\). Jean and Seo [8,11] introduced two new fault-tolerant LD sets, RED:LD and ERR:LD sets, and fully characterized and established existence criteria for RED:LD, DET:LD, and ERR:LD sets; these characterizations are included in this paper as Theorems 1.2, 1.3, and 1.4, respectively. Note that characterizations of general fault-tolerant variants of distinguishing sets were established by Seo and Slater [18], though their general analysis does not cover LD set variants due to an assumption that each vertex has only one detection region. Jean and Seo [10] also proved upper and lower bounds for optimal FTLD sets in SQ: \(\left[\frac{2}{5}, \frac{7}{16}\right]\) for RED:LD, \(\left[\frac{12}{23}, \frac{7}{12}\right]\) for DET:LD (improved from [21]), and \(\left[\frac{24}{37}, \frac{2}{3}\right]\) for ERR:LD.
A variety of graphical parameters have been studied on the infinite king grid [2,3,5,14]; for instance, Charon et al. [1] proved \(\textrm{IC}(\textrm{K}) = \frac{2}{9}\), Honkala and Laihonen [4] determined that \(\textrm{LD}(\textrm{K}) = \frac{1}{5}\), Seo [16] found that \(\frac{6}{25} \leq \textrm{OLD}(\textrm{K}) \leq \frac{1}{4}\), and Jean and Seo [7] proved \(\frac{3}{10} \leq \textrm{RED:OLD}(\textrm{K}) \leq \frac{1}{3}\) and \(\frac{3}{11} \leq \textrm{RED:IC}(\textrm{K}) \leq \frac{1}{3}\).
Similar types of fault-tolerant open-locating-dominating sets on other infinite graphs have also been studied; for instance on the infinite hexagonal grid (HEX) and the infinite triangular grid (TRI). Seo and Slater [18] proved that \(\textrm{RED:OLD}(\textrm{HEX}) = \frac{2}{3}\), \(\textrm{DET:OLD}(\textrm{HEX}) = \frac{6}{7}\), \(\textrm{RED:OLD}(\textrm{SQ}) = \frac{1}{2}\), \(\textrm{DET:OLD}(\textrm{SQ}) = \frac{3}{4}\), \(\textrm{RED:OLD}(\textrm{TRI}) = \frac{3}{8}\), and \(\textrm{DET:OLD}(\textrm{TRI}) \le \frac{5}{9}\). Later, Jean and Seo [9] proved that \(\textrm{DET:OLD}(\textrm{TRI}) = \frac{1}{2}\).
In this section, we explain the concepts of “share” and “discharging,” which will be used in Section 4 to prove the lower bounds for FTLD sets in the infinite king grid. We also introduce several notations that will be used to shorten these proofs.
Instead of finding a lowerbound for the optimal density directly, it is often easier to find an upperbound for the average “contribution” of each detector vertex to the domination of its neighbors. This “contribution” is measured by the share of a detector vertex, which was first introduced by Slater [21]. Let \(S \subseteq V(G)\) be a set of LD detectors.
Definition 3.1. The domination count of a vertex \(v \in V(G)\), denoted \(\operatorname{dom}(v)\), is \(|N[v] \cap S|\).
Definition 3.2. The partial share of a vertex \(v \in V(G)\), denoted \(\operatorname{sh}[v]\), is \(\frac{1}{\operatorname{dom}(v)}\).
Definition 3.3. The (total) share of a detector vertex \(v \in S\), denoted \(\operatorname{sh}(v)\), is \(\sum\limits_{u \in D}{\operatorname{sh}[u]}\) where \(D\) is the set of vertices dominated by \(v\).
For LD detectors, \(\operatorname{dom}(v) = |N[v] \cap S|\) and \(\operatorname{sh}(v) = \sum\limits_{u \in N[v]}{\operatorname{sh}[u]}\). If \(S\) is a dominating set—that is, \(\forall v \in V(G)\), \(\operatorname{dom}(v) \ge 1\)—it is clear that for a finite graph, \(\sum\limits_{x \in S}{\operatorname{sh}(x)} = |V(G)|\) because each vertex which is \(k\)-dominated has partial share \(\frac{1}{k}\) and this fraction is repeated \(k\) times due to having \(k\) dominators. Thus, the average share will be equal to \(\frac{|V(G)|}{|S|}\), the inverse density of \(S\) in \(V(G)\). When \(G\) has the slow-growth property, this equivalence between the average share and the inverse density extends even to infinite graphs [15].
Definition 3.4. For some \(A \subseteq V(G)\), let \(\operatorname{sh}[A]\) denote the block share of \(A\), \(\sum\limits_{x \in A}{\operatorname{sh}[x]}\).
For example, \(\operatorname{sh}[\{v_1,v_2\}] = \operatorname{sh}[v_1] + \operatorname{sh}[v_2]\), though we often shorten this to \(\operatorname{sh}[v_1v_2]\).
Notation 3.5. Let \(D_k\) denote the set of vertices which are exactly \(k\)-dominated, \(\{v \in V(G) : \operatorname{dom}(v) = k\}\), and \(D_{k+}\) denote the set of vertices which are at least \(k\)-dominated, \(\cup_{j \ge k}{D_j}\).
Notation 3.6. Let \(\sigma_A\) be \(\sum\limits_{x \in A}{\frac{1}{x}}\) where \(A\) is a finite sequence of single-character symbols denoting natural numbers (e.g. \(\sigma_{123} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3}\) or \(\sigma_{abc} = \frac{1}{a} + \frac{1}{b} + \frac{1}{c}\) where \(a,b,c \in \mathbb{N}\)).
Consider the graph \(G\) in Figure 1, where shaded vertices represent detectors, elements of RED:LD set \(S= \{v_1, v_2,v_4,v_6\}\). We observe that \(\{v_5,v_6\} \subseteq D_2\), \(\{v_1,v_3,v_4\} \subseteq D_3\), and \(v_2 \in D_4\), thus \(\operatorname{sh}[v_5] = \operatorname{sh}[v_6] = \frac{1}{2}\), \(\operatorname{sh}[v_1] = \operatorname{sh}[v_3] = \operatorname{sh}[v_4] = \frac{1}{3}\), and \(\operatorname{sh}[v_2] = \frac{1}{4}\). Therefore, \(\operatorname{sh}(v_1) = \operatorname{sh}[N[v_1]] = \operatorname{sh}[v_1v_2v_4v_5] = \sigma_{3432} = \frac{17}{12}\) and \(\operatorname{sh}(v_2) = \operatorname{sh}[N[v_2]] = \operatorname{sh}[v_1v_2v_3v_4v_6] = \sigma_{34332} = \frac{7}{4}\). Similarly, we can show that \(\operatorname{sh}(v_4) = \frac{7}{4}\) and \(\operatorname{sh}(v_6) = \frac{13}{12}\). We see that the sum of shares for the dominating set \(S\) is \(\frac{17}{12} + \frac{7}{4} + \frac{7}{4} + \frac{13}{12} = 6 = |V(G)|\), as expected, and the average is indeed \(\frac{6}{4} = \frac{3}{2}\), the inverse density. Although it is not shown, using \(S = V(G)\) in the example graph from Figure 1 would be an ERR:LD set, and using \(S = V(G) – \{v_3\}\) would be a DET:LD set.
In proving a maximum (target) value for the average share of all detector vertices, we would ideally like to prove a maximum value for the share of any individual detector vertex, as this would necessarily be a maximum for the average as well. However, in doing so we might run into “problem cases” where the share of a detector vertex exceeds our target. In these cases we must prove that said problem case also induces one or more other detector vertices with sufficiently low share that the average will still be bounded by the target. To prove this bound for the average share, we apply a discharging argument, in which we attempt to distribute the excess share of each problematic detector vertex to other detectors with share values below the target. So long as the final result after discharging ensures that each detector has a share value no more than the target, the bound on the average share is proven. This operation is sound because the sum of shares, and therefore the average share, remains the same. The full proof of this soundness is presented in [15].
When discussing problem cases, we consider having a “center” vertex, say \(x\), which is assumed to have \(\operatorname{sh}(x) > t\) where \(t\) is the target. In order for the discharging argument to be valid, we require that \(\forall u \in S\), \(\widehat{sh}(u) \le t\), where \(\widehat{sh}(u)\) denotes the share value of \(u\) after discharging. Naturally, the precise definition of \(\widehat{sh}(u)\) depends on the specific method used to perform discharging; in this paper, we allow discharging only to neighbors. For any \(v \in N(x) \cap S\) with \(\max \operatorname{sh}(v) < t\)—where \(\max \operatorname{sh}(v)\) denotes the maximum possible share value of \(v\) in the current context of which vertices are known to be detectors or non-detectors—\(v\) can accept at most \(t – \max \operatorname{sh}(v)\) discharge in total. However, there may exist multiple problematic vertices adjacent to \(v\) which could attempt to discharge to \(v\), and we must ensure that the total transfer to \(v\) does not exceed \(t – \max \operatorname{sh}(v)\). To guarantee this, we will conservatively limit the transfer from \(x\) to \(\frac{1}{k(v)}(t – \max \operatorname{sh}(v))\) where \(k(v) \ge 1\) denotes an upper bound on the number of problematic vertices which could simultaneously attempt to discharge to \(v\), including \(x\) itself. Thus, the discharging arguments in this paper will use \(\widehat{sh}(x) = \operatorname{sh}(x) – \sum\limits_{v \in N(x) \cap S} \frac{1}{k(v)}\max(t – \max \operatorname{sh}(v), 0)\). This ensures that each discharging target, \(v\), which is implied to have \(\max \operatorname{sh}(v) < t\), receives at most \(\frac{1}{k(v)}(t – \max \operatorname{sh}(v))\) discharge from at most \(k(v)\) problematic neighbors, for a total of at most \(t – \max \operatorname{sh}(v)\), implying \(\widehat{sh}(v) \le \max \operatorname{sh}(v) + (t – \max \operatorname{sh}(v)) = t\).
This strategy differs from other discharging approaches which have been used in that it works backwards: instead of determining the excess share of a problem vertex and dividing it equally to its neighbors, we determine for each neighbor the amount of discharge it can receive from the problem vertex. Instead of uniform outgoing discharge from the problem case, we have uniform incoming discharge to the non-problem neighbors. This technique is perhaps more powerful for problem cases with asymmetric shares; that is, where the maximum shares of discharge targets are not equal.
Algorithm 1. Problem case resolution algorithm
Algorithm 1 formalizes the logic behind the discharging technique we have described. Suppose we have some vertex \(x \in S\) with \(\operatorname{sh}(x) > t\); this problem case can be resolved if Algorithm 1 returns \(true\), given arguments \(x\) and \(t\). Note that although Algorithm 1 examines all \(v \in N(x) \cap S\) to calculate \(\widehat{sh}(x)\), this is not strictly necessary as \(\widehat{sh}(x) \le p\), implying \(p \le t\) could be used as an early exit condition.
In this section we will determine upper and lower bounds for the optimal (minimum) densities of RED:LD, DET:LD, and ERR:LD sets on the infinite king grid, \(\textrm{K}\). Firstly, for the upper bound, we have constructed LD, RED:LD, DET:LD, and ERR:LD sets on the infinite king grid with densities \(\frac{1}{5}\), \(\frac{5}{16}\), \(\frac{6}{16}\), and \(\frac{7}{16}\), respectively, as shown in Figure 2 (note that Figure 2 (a) was found to be isomorphic to a previous solution by Honkala and Laihonen [4]). One may verify that each of these constructions are valid detection systems using Theorems 1.1, 1.2, 1.3, and 1.4, respectively.
As an example of verifying these upper bound solutions, we will show Figure 2 (d) is an ERR:LD set using the labeling from Figure 3. First, we must verify that each vertex \(u \in V(\textrm{K})\) is at least 3-dominated. Because \(S\) is formed from a periodic tiling of the shaded region of Figure 3, we can assume without loss of generality that \(u\) lies within the tile. This simplifies the verification of \(u\) being at least 3-dominated from an infinite number of values of \(u\) to only 16 equivalence classes, one for each vertex in the tile. We can exhaustively check that each such \(u\) is at least 3-dominated, so \(S\) satisfies property i) of Theorem 1.4. Next, we will check that every vertex pair \(u,v \in V(G)\) with \(u \neq v\) is 3-distinguished. If \(d(u,v) \ge 3\), then clearly the pair is 6-distinguished because each is at least 3-dominated and no single detector can dominate both of them; thus, we need only consider when \(d(u,v) \le 2\). Similar to the verification of 3-domination, we may assume without loss of generality that \(u\) lies within the tile, meaning we need only consider the finite choices of \(v\) with \(d(u, v) \le 2\); this is precisely the region of K shown in Figure 3.
As the number of cases for \((u,v)\) is finite, it can be shown by exhaustion that every vertex pair \((u,v)\) is 3-distinguished, implying \(S\) is an ERR:LD set on K. For example, take the detector pair \((v_{c3}, v_{d3})\): aside from themselves, they are dominated by \(v_{b2}\), \(v_{e3}\), and \(v_{d4}\); however \(v_{d4}\) is common to both. Thus, \(v_{c3}\) and \(v_{d3}\) are 2-distinguished; they need only be 1-distinguished, so they are distinguished. As another example, take the detector pair \((v_{e5},v_{d7})\): they have no common detectors, and are clearly 5-distinguished, so they are distinguished. Consider the non-detector pair \((v_{f4},v_{f5})\); we see they are 3-distinguished by \(v_{e3}\), \(v_{g3}\), and \(v_{f6}\), and therefore meet the minimum requirements to be distinguished. We also see the non-detector pair \((v_{f5},v_{g6})\) are 3-distinguished by \(v_{e5}\), \(v_{g7}\), and \(v_{h7}\), and are thus distinguished. Consider the mixed pair \((v_{c5},v_{d5})\); we find they are 2-distinguished by \(v_{b6}\) and \(v_{e5}\), and thus satisfy the minimum requirements to be distinguished. As another example, we see the mixed pair \((v_{d2},v_{d4})\) is 4-distinguished by \(v_{c1}\), \(v_{e1}\), \(v_{c5}\), and \(v_{e5}\), and thus is distinguished. As all pairs can be shown to be distinguished by exhaustion, \(S\) is an ERR:LD set. Thus, we have an upper bound for the optimal density: \(\textrm{ERR:LD}(\textrm{K}) \le \frac{7}{16}\).
Using this same technique of examining only a single tile of the periodic construction and all vertices within distance 2 by exhaustion, we can verify that the tilings in (a), (b), and (c) from Figure 2 satisfy the requirements of Theorems 1.1, 1.2, and 1.3, respectively, so we have the following upper bounds for the optimal densities: \(\textrm{RED:LD}(\textrm{K}) \le \frac{5}{16}\) and \(\textrm{DET:LD}(\textrm{K}) \le \frac{6}{16}\). Figure 2 shows an upper bound of \(\frac{1}{5}\) for \(\textrm{LD}(\textrm{K})\), which has already been proven to be optimal [4]; it is included for comparison purposes.
With upper bounds for each parameter now established, we will proceed to explore lower bounds for these sets. If \(S\) is a RED:LD set, then Theorem 1.2 guarantees every \(v \in V(\textrm{K})\) must be 2-dominated, so \(\operatorname{sh}[v] \le \frac{1}{2}\); thus, \(\forall x \in S\), \(\operatorname{sh}(x) \le 9 \times \frac{1}{2} = \frac{9}{2}\), giving us a simple lower bound: \(\textrm{RED:LD}(\textrm{K}) \ge \frac{2}{9}\). Similarly, by Theorems 1.3 and 1.4, we find that \(\textrm{DET:LD}(\textrm{K}) \ge \frac{2}{9}\) and \(\textrm{ERR:LD}(\textrm{K}) \ge \frac{3}{9} = \frac{1}{3}\). However, these simple lower bounds can be greatly improved by applying the discharging technique we have described. In what follows, we will use this technique to improve these bounds for RED:LD and ERR:LD to \(\frac{3}{11}\) and \(\frac{15}{38}\), respectively.
Theorem 4.1. Let \(S \subseteq V(G)\) be an ERR:LD set for the king’s grid. Then, the average share of all vertices in \(S\) is at most \(\frac{38}{15}\).
Proof. Let \(S \subseteq V(G)\) be an ERR:LD set on \(\textrm{K}\), let the notations \(sh\), \(dom\), and \(k\)-dominated implicitly use \(S\), and let a vertex pair being distinguished denote satisfying the relevant pair property of Theorem 1.4. Let \(x \in S\) be a detector vertex; Theorem 1.4 yields that \(|N[x] \cap S| \ge 3\). There are eight non-isomorphic ways to at least 3-dominate \(x\), as shown in Figure 4. Square vertices represent detectors (shaded) or non-detectors (non-shaded), and round vertices denote unknowns. Note that vertices are labeled with numbers such as \(k\), but will be referenced in the text as \(v_k\).
Case L. First, we consider the partial shares of vertices \(A = \{x,v_1,v_2,v_3\}\). We require \(|A \cap D_{4+}| \ge 2\) for the vertices in \(A\) to be distinguished. Suppose \(v_2\) is a non-detector. Let \(d = \min_{w \in \{x,v_1,v_3\}}{\operatorname{dom}(w)}\). If \(d = 3\) then \(\operatorname{dom}(v_2) \ge 5\) to be distinguished; if \(d = 4\) then \(\operatorname{dom}(v_2) \ge 4\) to be distinguished; otherwise \(d \ge 5\) and \(\operatorname{dom}(v_2) \ge 3\). Thus, \(\operatorname{sh}[xv_1v_2v_3] \le \max \{ \sigma_{3445}, \sigma_{3445}, \sigma_{4444}, \sigma_{5553}\} = \frac{31}{30}\). Otherwise, \(v_2\) is a detector; in order to distinguish it from the other three detectors, \(x\), \(v_1\), and \(v_3\), we need \(\operatorname{sh}[xv_1v_2v_3] \le \sigma_{4555} < \frac{31}{30}\). In either case, \(\operatorname{sh}[xv_1v_2v_3] \le \frac{31}{30}\).
Next, we consider the partial shares of \(v_4\) and \(v_5\). If both are detectors, then \(\operatorname{sh}[v_4v_5] \le \sigma_{45}\) to be distinguished. If both are non-detectors, then \(\operatorname{sh}[v_4v_5] \le \sigma_{34}\) to be distinguished. Otherwise, we let \(v_1\) be unknown to allow symmetry between \(v_4\) and \(v5\); then by symmetry let \(\{v_4,v_5\} \cap S = \{v_4\}\); then \(\operatorname{sh}[v_4v_5] \le \max \{\sigma_{35},\sigma_{44}\}\). Thus, \(\operatorname{sh}[v_4v_5] \le \sigma_{34}\), and by symmetry, \(\operatorname{sh}[v_7v_8] \le \sigma_{34}\) as well. Therefore, \(\operatorname{sh}(x) = \operatorname{sh}[xv_1v_2v_3] + \operatorname{sh}[v_4v_5] + \operatorname{sh}[v_6] + \operatorname{sh}[v_7v_8] \le \sigma_{3445} + \sigma_{34} + \sigma_3 + \sigma_{34} = \frac{38}{15}\), and we are done.
Case Triangle. Next, we consider the case where \(x\) is dominated by two neighbors in a “triangle” shape, as in Figure 6. We will assume that \(\{v_3,v_7\} \cap S = \varnothing\), as otherwise we fall into the previous case.
We consider \(\operatorname{sh}[xv_1v_2v_3]\), \(\operatorname{sh}[v_7v_8]\), and \(\operatorname{sh}[v_4v_5v_6]\). First, if \(\operatorname{dom}(v_3) = 3\), then \(\{x,v_1,v_2\} \subseteq D_{5+}\) to distinguish from \(v_3\), so \(\operatorname{sh}[xv_1v_2v_3] \le \sigma_{3555}\); if \(\operatorname{dom}(v_3) = 4\), then \(\operatorname{sh}[xv_1v_2v_3] \le \sigma_{4444}\) to be distinguished; otherwise \(\operatorname{dom}(v_3) \ge 5\), in which case \(\operatorname{sh}[xv_1v_2v_3] \le \sigma_{3445}\). Therefore, \(\operatorname{sh}[xv_1v_2v_3] \le \sigma_{3445}\). If \(v_8 \in S\), then \(\operatorname{sh}[v_7v_8] \le \max \{\sigma_{35}, \sigma_{44}\} < \sigma_{34}\); otherwise, \(\operatorname{sh}[v_7v_8] \le \sigma_{34}\). If \(\{v_4, v_5, v_6\} \cap D_{4+} \neq \varnothing\), then \(\operatorname{sh}(x) = \operatorname{sh}[xv_1v_2v_3] + \operatorname{sh}[v_4v_5v_6] + \operatorname{sh}[v_7v_8] \le \sigma_{3445} + \sigma_{334} + \sigma_{34} = \frac{38}{15}\) and we will be done.
Otherwise, we assume \(\{v_4, v_5, v_6\} \subseteq D_3\); we consider the following sub-cases depending on whether these three vertices are detectors or not.
Subcase 1. If \(\{v_4,v_5,v_6\} \cap S = \varnothing\), then \(v_5\) needs two additional detectors, but at least one of them will be in \(N(v_4)\); thus, \(v_4\) and \(v_5\) are not distinguished, a contradiction.
Subcase 2. If \(\{v_4,v_5,v_6\} \cap S = \{v_5\}\), then \(v_4\) and \(v_6\) are not distinguished, a contradiction.
Subcase 3. If \(\{v_4,v_5,v_6\} \cap S = \{v_6\}\), then \(v_5\) needs one additional detector, \(w \in S\); if \(w \in N(v_4)\) then \(\{v_4,v_5\}\) are not distinguished, a contradiction; otherwise \(w = v_{18}\) and \(\{v_5,v_6\}\) are not distinguished, a contradiction.
Similarly, if \(\{v_4,v_5,v_6\} \cap S = \{v_4\}\) then we reach a contradiction.
Subcase 4. If \(\{v_4,v_5,v_6\} \cap S = \{v_4,v_5\}\) then \(v_4\) and \(v_5\) are not distinguished, a contradiction; similarly, if \(\{v_4,v_5,v_6\} \cap S = \{v_5,v_6\}\) then \(v_5\) and \(v_6\) are not distinguished, contradiction.
Subcase 5. If \(\{v_4,v_5,v_6\} \cap S = \{v_4,v_6\}\), consider the third dominator for \(v_6\).
If \(v_{17} \in S\) or \(v_{18} \in S\) is the third dominator, we get \(\operatorname{dom}(v_5) \ge 4\), a contradiction. If \(v_{20} \in S\) or \(v_{21} \in S\) is the third dominator, then we need \(v_8 \in S\) or \(v_{22} \in S\) to distinguish \(v_7\) from \(v_6\), which in turn will make \(\operatorname{dom}(v_7) \ge 5\) and \(\operatorname{dom}(v_8) \ge 4\); thus \(\operatorname{sh}(x) = \operatorname{sh}[xv_1v_2v_3] + \operatorname{sh}[v_4v_5v_6] + \operatorname{sh}[v_7v_8] \le \sigma_{3445} + \sigma_{333} + \sigma_{45} < \frac{38}{15}\). Otherwise, \(v_{19} \in S\) is the third dominator. Then we need \(v_8 \in S\) or \(v_{22} \in S\) to distinguish \(v_7\) from \(v_5\), which will make \(\operatorname{dom}(v_7) \ge 4\) and \(\operatorname{dom}(v_8) \ge 4\); thus \(\operatorname{sh}(x) = \operatorname{sh}[xv_1v_2v_3] + \operatorname{sh}[v_4v_5v_6] + \operatorname{sh}[v_7v_8] \le \sigma_{3445} + \sigma_{333} + \sigma_{44} = \frac{38}{15}\), completing the proof of the triangle case.
Case Bent. Consider the case where \(x\) is dominated by two neighbors in a “bent” shape, as in Figure 7. We will assume that \(\{v_2, v_3, v_5, v_7, v_8\} \cap S = \varnothing\), as otherwise we fall into previous cases.
First, we consider when \(v_6 \in S\), then \(\operatorname{dom}(x) = 4\). We observe that \(\{v_3,v_5,v_7\} \subseteq D_{4+}\) to be distinguished from \(x\). We now consider how to 4-dominate \(v_7\). Suppose \(v_{20} \notin S\), then \(\{v_{21},v_{22}\} \cap S \neq \varnothing\), and we observe that \(\operatorname{dom}(v_8) \ge 5\) to be distinguished from \(v_7\), so \(\operatorname{sh}(x) \le \frac{38}{15}\) and we are done. Thus, we assume that \(v_{20} \in S\). If \(\{v_{21},v_{22}\} \cap S \neq \varnothing\) then again \(\operatorname{dom}(v_8) \ge 5\) to be distinguished from \(v_7\) and we are done; so we assume \(\{v_{21},v_{22}\} \cap S = \varnothing\). By symmetry, we can assume that \(\{v_{12},v_{13},v_{14}\} \cap S = \{v_{14}\}\). If \(\{v_2,v_8\} \subseteq D_{4+}\) we are done, so without loss of generality we assume \(\operatorname{dom}(v_8) = 3\). If \(v_{23} \in S\) then \(v_1\) and \(v_2\) cannot be distinguished, a contradiction. Otherwise \(v_{24} \in S\) or \(v_9 \in S\); in either case, \(v_1\) and \(v_8\) cannot be distinguished, a contradiction. Therefore, \(\operatorname{sh}(x) \le \frac{38}{15}\).
Finally, we consider when \(v_6 \notin S\). We observe that \(\operatorname{dom}(v_3) \ge 5\) to be distinguished from \(x\), which in turn requires \(\operatorname{dom}(v_2) \ge 4\) to distinguish it from \(v_3\); thus, \(\operatorname{sh}[xv_2v_3] \le \sigma_{345}\). Next, we consider \(\operatorname{sh}[v_1v_7v_8]\) based on \(\operatorname{dom}(v_7)\). If \(v_7\) is 5-dominated, then we need \(\operatorname{dom}(v_8) \ge 6\) to distinguish it from \(v_7\). If \(v_7\) is 4-dominated with \(\{v_{20},v_{21}\}\) or \(\{v_{20},v_{22}\}\), we need \(\operatorname{dom}(v_8) \ge 5\) to distinguish from \(v_7\); otherwise, \(v_7\) is 4-dominated with \(\{v_{21},v_{22}\}\) and we need \(\operatorname{dom}(v_8) \ge 7\) to distinguish from \(v_7\). If \(v_7\) is 3-dominated with \(v_{21}\) or \(v_{22}\), we need \(\operatorname{dom}(v_8) \ge 6\) to distinguish from \(v_7\); otherwise, \(v_7\) is 3-dominated with \(v_{21}\) and we need \(\operatorname{dom}(v_8) \ge 4\), which in turn requires \(\operatorname{dom}(v_1) \ge 4\). From the three cases of \(\operatorname{dom}(v_7)\), we have \(\operatorname{sh}[v_1v_7v_8]\le \sigma_{344}\). If \(\{v_4,v_5,v_6\} \cap D_{4+} \neq \varnothing\) then we will be done because \(\operatorname{sh}(x) = \operatorname{sh}[xv_2v_3] + \operatorname{sh}[v_4v_5v_6] + \operatorname{sh}[v_1v_7v_8] \le \sigma_{345} + \sigma_{334} + \sigma_{344} \le \frac{38}{15}\). Otherwise, we assume \(\{v_4,v_5,v_6\} \subseteq D_3\). Then, we observe \(\{v_{15},v_{16},v_{17}\} \cap S = \varnothing\) because \(v_4\) is already 3-dominated, which in turn requires \(v_{18} \in S\) to 3-dominate \(v_5\). We find that \(v_5\) and \(v_6\) are not distinguished, a contradiction, completing the proof for Case Bent.
Case Vertical. Consider the case where when \(x\) is dominated in a “vertical” shape, as in Figure 8. We can assume that \(\{v_2, v_3, v_4, v_6, v_7, v_8\} \cap S = \varnothing\), as otherwise we fall into previous cases. We observe that \(\operatorname{dom}(v_3) \ge 5\) to be distinguished from \(x\). Further, \(\{v_2,v_4\} \subseteq D_{4+}\) to be distinguished from \(v_3\), thus \(\operatorname{sh}[v_2v_3v_4] \le \sigma_{454}\). By symmetry, we have \(\operatorname{sh}[v_6v_7v_8]\le \sigma_{454}\), as well. Therefore, \(\operatorname{sh}(x) = \operatorname{sh}[xv_1v_5]+ \operatorname{sh}[v_2v_3v_4] +\operatorname{sh}[v_7v_8v_9]\le \sigma_{333} + \sigma_{454} + \sigma_{454} \le \frac{38}{15}\), and we are done.
Case X. Consider the case where \(x\) is dominated by four neighbors in a “X” shape, as in Figure 9. We can assume that \(\{v_1,v_3,v_5,v_7\} \cap S = \varnothing\), as otherwise we fall into previous cases.
Suppose \(\{v_1,v_3,v_5,v_7\} \subseteq D_{4+}\), then \(\operatorname{sh}(x) \le \frac{38}{15}\) and we are done; otherwise, without loss of generality we assume \(\operatorname{dom}(v_7) = 3\). Then \(\{v_1,v_5\} \subseteq D_{4+}\) to be distinguished from \(v_7\). Suppose \(\operatorname{dom}(v_3) \ge 4\). If \(v_{14} \notin S\), then \(\operatorname{dom}(v_2) \ge 4\) to be distinguished from \(v_3\) and we are done; thus, we assume with symmetry that \(\{v_{12},v_{14}\} \subseteq S\). If \(v_{13} \in S\), then \(\operatorname{dom}(v_2) \ge 4\) and we are done, so we assume \(v_{13} \notin S\). If \(\operatorname{dom}(v_2) \ge 4\) we are done, so we assume \(\{v_9,v_{10},v_{11}\} \cap S = \varnothing\), requiring \(v_{24} \in S\) to 3-dominate \(v_1\). If \(\operatorname{dom}(v_8) \ge 4\) we are done, otherwise we find \(v_1\) and \(v_8\) are not distinguished, a contradiction. Now, we can assume \(\{v_3,v_7\} \subseteq D_3\) and examine \(\operatorname{dom}(v_1)\) and \(\operatorname{dom}(v_5)\). Without loss of generality we can assume \(\operatorname{dom}(v_1) \le \operatorname{dom}(v_5)\); then \((\operatorname{dom}(v_1), \operatorname{dom}(v_5)) \in \{(4, 4), (4, 5), (4, 6), (5, 5), (5, 6), (6, 6)\}\) and consider the following four sub-cases: where \(\operatorname{dom}(v_5) = 6\), and the other three possibilities.
First, if \(\operatorname{dom}(v_5) = 6\), then it requires \(\{v_{16},v_{17},v_{18}\} \subseteq S\), which implies that \(\{v_4,v_6\} \subseteq D_4\), so \(\operatorname{sh}(x) = \operatorname{sh}[xv_2v_3v_7v_8] + \operatorname{sh}[v_1v_5] + \operatorname{sh}[v_4v_6] \le \sigma_{53333}+ \sigma_{46} +\sigma_{44} \le \frac{38}{15}\). Second, assume \(\operatorname{dom}(v_1) = \operatorname{dom}(v_5) = 4\). If \(v_9 \in S\) to 4-dominate \(v_1\), then \(\{v_2,v_8\} \subseteq D_{4+}\) to distinguish from \(v_1\). Otherwise, \(v_{24} \in S\) or \(v_{10} \in S\), then \(\{v_2,v_8\} \cap D_{4+} \neq \varnothing\) to distinguish from \(v_1\). Hence, \(\operatorname{sh}[v_1v_2v_8] \le \sigma_{344}\) and by symmetry, we also have \(\operatorname{sh}[v_4v_5v_6] \le \sigma_{344}\). Therefore, \(\operatorname{sh}(x) = \operatorname{sh}[xv_3v_7] + \operatorname{sh}[v_1v_2v_8] + \operatorname{sh}[v_4v_5v_6] \le \sigma_{533} +\sigma_{344} + \sigma_{344} = \frac{38}{15}\) and we are done.
Next, assume \(\operatorname{dom}(v_1)=4\) and \(\operatorname{dom}(v_5)=5\). If \(v_9 \in S\), then we need \(\{v_2,v_8\} \subseteq D_{4+}\) for \(v_1\) to be distinguished from \(v_2\) and \(v_8\), and we get \(\operatorname{sh}(x) = \operatorname{sh}[xv_3v_7] + \operatorname{sh}[v_1v_2v_8] + \operatorname{sh}[v_4v_5v_6] \le \sigma_{533} +\sigma_{444} + \sigma_{353} = \frac{149}{60} < \frac{38}{15}\), so we are done; thus, we assume \(v_9 \notin S\). We need \(v_{10} \in S\) or \(v_{24} \in S\) to 4-dominate \(v_1\); by symmetry, let \(v_{24} \in S\), which requires \(v_{11} \in S\) to 3-dominate \(v_2\) and \(v_{23} \in S\) to distinguish \(v_8\) from \(v_1\). If \(v_{17} \in S\), then we need \(v_{16} \in S\) or \(v_{18} \in S\) to 5-dominate \(v_5\); by symmetry, let \(v_{16} \in S\), then \(\operatorname{dom}(v_4) \ge 5\) to be distinguished from \(v_5\) and we are done. Thus, we assume \(v_{17} \notin S\), requiring \(\{v_{16}, v_{18}\} \subseteq S\) to 5-dominate \(v_5\). If \(v_{15} \in S\) or \(v_{19} \in S\), then \(\operatorname{sh}(x) = \operatorname{sh}[xv_3v_7] + \operatorname{sh}[v_1v_2v_8] + \operatorname{sh}[v_4v_5v_6] \le \sigma_{533} +\sigma_{434} + \sigma_{453} \le \frac{38}{15}\), and we are done. Therefore, we assume \(v_{15} \notin S\) and \(v_{19} \notin S\), which leads us to the first problem configuration, which will be handled separately.
Lastly, assume \(\operatorname{dom}(v_1)=5\) and \(\operatorname{dom}(v_5)=5\). Similarly to the previous case, if \(v_{17} \in S\), then \(\operatorname{sh}(x) \le \frac{38}{15}\) and we are done, so with symmetry we assume \(v_{17} \notin S\) and \(v_9 \notin S\). Therefore, we require \(\{v_{10}, v_{24}, v_{16}, v_{18}\} \subseteq S\) to 5-dominate \(v_1\) and \(v_5\). If \(\{v_{11}, v_{15}, v_{19}, v_{23}\} \cap S \neq \varnothing\), then \(\operatorname{sh}(x) = \operatorname{sh}[xv_3v_7] + \operatorname{sh}[v_1v_5] + \operatorname{sh}[v_2v_4v_6v_8] \le \sigma_{533} +\sigma_{55} + \sigma_{3334} \le \frac{38}{15}\), and we are done. Thus, we assume \(\{v_{11}, v_{15}, v_{19}, v_{13}\} \cap S = \varnothing\), which leads to the second problem configuration, which will be handled separately.
In either of the Problem Cases, as shown in Figure 10, we see that \(\operatorname{sh}(x) \le \max \left\{\frac{77}{30},\frac{13}{5}\right\} = \frac{13}{5}\). To handle these problems, we consider the maximum share of \(v_4\), which will be the same in either configuration. We observe that we need \(\operatorname{dom}(v_{17}) \ge 6\) to distinguish from \(v_5\), \(\operatorname{dom}(v_{13}) \ge 4\) to distinguish from \(v_3\), and \(\operatorname{sh}[v_{14}v_{15}] \le \sigma_{34}\) to distinguish \(v_{14}\) from \(v_{15}\). Thus \(\operatorname{sh}(x) = \operatorname{sh}[xv_3v_4v_5v_{17}] + \operatorname{sh}[v_{13}v_{14}v_{15}v_{16}] = \sigma_{53356} + \sigma_{4343} = \frac{12}{5} < \frac{38}{15}\). Additionally, the only detector vertex adjacent to \(v_4\) other than \(x\) is \(v_{16}\), which previous cases have shown to have share at most \(\frac{38}{15}\). Thus, \(v_4\) can safely accept \(\frac{38}{15} – \frac{12}{5} = \frac{2}{15}\) from \(x\). Therefore, \(\widehat{sh}(x) \le \frac{13}{5} – \frac{2}{15} = \frac{37}{15} < \frac{38}{15}\) and we are done.
Case Lambda. Consider the case where \(x\) is dominated by three neighbors in a “lambda” shape, as in Figure 11. We will assume that \(\{v_1,v_3,v_5,v_7,v_8\} \cap S = \varnothing\), as otherwise we fall into previous cases.
Firstly, we observe that \(\{v_3,v_5\} \subseteq D_{4+}\) to be distinguish from \(x\); so \(\operatorname{sh}[xv_3v_5] \le \sigma_{444}\). Suppose \(\{v_{20},v_{21}\} \cap S \neq \varnothing\), then we find \(\operatorname{sh}[v_6v_7] \le \sigma_{35}\) to distinguish \(\{v_6,v_7\}\). By symmetry, \(\{v_{9},v_{10}\} \cap S \neq \varnothing\) implies \(\operatorname{sh}[v_1v_2] \le \sigma_{35}\). Therefore, if \(\{v_{20},v_{21}\} \cap S \neq \varnothing\) and \(\{v_9,v_{10}\} \cap S \neq \varnothing\), then \(\operatorname{sh}(x) \le \sigma_{444} + \sigma_{35} + \sigma_{35} + \sigma_{33} < \frac{38}{15}\) and we are done; otherwise by symmetry we assume that \(\{v_9,v_{10}\} \cap S = \varnothing\), requiring \(v_{24} \in S\) to 3-dominate \(v_1\). We then see that \(\operatorname{dom}(v_8) \ge 4\) to be distinguished from \(v_1\). Suppose \(\{v_{20},v_{21}\} \cap S \neq \varnothing\) then \(\operatorname{sh}[v_6v_7] \le \sigma_{35}\) and we are done; thus, we assume \(\{v_{20},v_{21}\} \cap S = \varnothing\), requiring \(\{v_{22},v_{23}\} \subseteq S\) to 4-dominate \(v_8\). If \(\{v_{12},v_{13}\} \cap S \neq \varnothing\), then \(\operatorname{sh}[v_2v_3] \le \sigma_{35}\) and we are done; thus, by symmetry, we assume that \(\{v_{12},v_{13},v_{17},v_{18}\} \cap S = \varnothing\), requiring \(v_{11} \in S\) and \(v_{19} \in S\) to 3-dominate \(v_2\) and \(v_6\), respectively. Additionally, we require \(v_{14} \in S\) and \(v_{16} \in S\) to 4-dominate \(v_3\) and \(v_5\), respectively. If \(v_{15} \in S\) then \(\operatorname{dom}(v_4) \ge 5\) and we are done, so we assume \(v_{15} \notin S\), leading to the configuration shown in Figure 12.
To handle this problem case, we look at the share of \(v_4\). We observe that we need \(\operatorname{dom}(v_{15}) \ge 4\) and \(\operatorname{dom}(v_{13}) \ge 5\) to be distinguished from \(v_4\) and \(v_3\), respectively. Therefore, \(\operatorname{sh}(v_4) \le \frac{2}{5} +\frac{5}{4} +\frac{2}{3} = \frac{139}{60}\). Additionally, \(v_4\) is only adjacent to \(v_{14}\) and \(v_{16}\), which preceding Cases have proven to have share at most \(\frac{38}{15}\). Thus, \(v_4\) has no neighboring detectors with share exceeding \(\frac{38}{15}\) other than \(x\) itself, so it can safely accept \(\frac{38}{15} – \frac{139}{60} = \frac{13}{60}\) discharge from \(x\). Therefore, \(\widehat{sh}(x) \le \frac{31}{12} – \frac{13}{60} = \frac{71}{30} < \frac{38}{15}\) and we are done.
Case Diagonal. Consider the case where \(x\) is dominated by two neighbors in a “diagonal” shape, as in Figure 13. We can assume that \(\{v_1, v_3, v_4,v_5,v_7, v_8\} \cap S = \varnothing\), as otherwise we fall into previous cases. As this case is perhaps the most complicated, we will begin by proving two smaller claims:
Claim 1. \(|\{w \in A : \operatorname{dom}(w) = 3\}| \le 1\) for \(A = \{v_1,v_3\}\) or \(A = \{v_5,v_7\}\).
Proof. By symmetry, we need only examine one event: suppose that \(\operatorname{dom}(v_1) = \operatorname{dom}(v_3) = 3\); then \(v_1\) and \(v_3\) are not distinguished, a contradiction. ◻
Claim 2. If \(\operatorname{dom}(v_1) \ge k\) or \(\operatorname{dom}(v_3) \ge k\) in the diagonal configuration, then \(\operatorname{dom}(v_2) \ge k\).
Proof. By Theorem 1.4, we know \(k \le 3\) is always satisfied, and vertices \(v_1\) and \(v_3\) can be at most 5-dominated, so we consider two cases: \(k = 4\) and \(k = 5\).
For \(k = 4\), without loss of generality assume to the contrary that \(\operatorname{dom}(v_3) \ge 4\) but \(\operatorname{dom}(v_2) \le 3\). We see that \(v_2\) is already dominated by itself and \(x\), and we consider the third dominator for \(v_2\). If \(\{v_9, v_{10}, v_{11}\} \cap S \neq \varnothing\), then \(\operatorname{dom}(v_3) < 4\), a contradiction; thus, we assume \(\{v_9, v_{10}, v_{11}\} \cap S = \varnothing\). We see that \(v_2\) and \(v_3\) are not distinguished, a contradiction.
For \(k = 5\), without loss of generality, assume to the contrary that \(\operatorname{dom}(v_3) \ge 5\) but \(\operatorname{dom}(v_2) \le 4\). We require \(\{v_{12}, v_{13}, v_{14}\} \subseteq S\) to 5-dominate \(v_3\); thus \(\operatorname{dom}(v_2) \ge 4\), so \(\operatorname{dom}(v_2) = 4\) and we observe that \(v_2\) and \(v_3\) are not distinguished, a contradiction. ◻
By symmetry, Claim 2 also applies to \(\operatorname{dom}(v_5)\) and \(\operatorname{dom}(v_7)\) influencing \(\operatorname{dom}(v_6)\).
Resuming with the diagonal case expansion, suppose \(\{v_9,v_{10}\} \cap S = \varnothing\), then \(\operatorname{dom}(v_1) = 3\) with \(v_{24} \in S\). Then Claim 1 yields that \(\operatorname{dom}(v_3) \ge 4\), and Claim 2 yields that \(\operatorname{dom}(v_2) \ge 4\). Additionally, \(\{v_5,v_7\} \cap D_{4+} \neq \varnothing\), implying \(\operatorname{dom}(v_6) \ge 4\). We also require \(\operatorname{dom}(v_8) \ge 4\) to be distinguished from \(v_1\). We now have five 4-dominated vertices; if we have any more or if any of them is at least 5-dominated then we are done. Thus, we will assume \(\{v_1,v_4\} \subseteq D_3\), \(\{v_2,v_3,v_6,v_8\} \subseteq D_4\), and \((\operatorname{dom}(v_5),\operatorname{dom}(v_7)) \in \{(3,4),(4,3)\}\). If \(\{v_{17},v_{18}\} \subseteq S\) then \(v_5\) and \(v_6\) are not distinguished, a contradiction. If \(\{v_{17},v_{18}\} \cap S = \varnothing\), then \(v_4\) and \(v_5\) are not distinguished, a contradiction. Therefore, we assume \(|\{v_{17},v_{18}\} \cap S| = 1\); then \(\operatorname{dom}(v_5) = 4\) to be distinguished from \(v_6\), requiring \(\operatorname{dom}(v_7) = 3\). If \(v_{20} \in S\) then \(v_6\) and \(v_7\) are not distinguished, a contradiction, so we assume \(v_{20} \notin S\); similarly, we can assume \(v_{21} \notin S\), requiring \(\{v_{22},v_{23}\} \subseteq S\). If \(\{v_{12},v_{13}\} \subseteq S\) then \(v_2\) and \(v_3\) are not distinguished, a contradiction. If \(\{v_{12},v_{13}\} \cap S = \varnothing\) then \(\operatorname{dom}(v_2) = 3\), a contradiction. Therefore, we assume \(|\{v_{12},v_{13}\} \cap S| = 1\), providing symmetry with \(\{v_{17},v_{18}\}\). If \(v_{18} \notin S\) then \(v_4\) and \(v_5\) are not distinguished, a contradiction, so we assume \(v_{18} \in S\), requiring \(v_{17} \notin S\); by symmetry \(v_{12} \in S\) and \(v_{13} \notin S\). Then we require \(\{v_{16},v_{19}\} \subseteq S\) and \(\{v_{11},v_{14}\} \subseteq S\). Finally, \(v_{15} \notin S\) because \(\operatorname{dom}(v_4) = 3\). This gives us Problem Case 1, which will be handled separately.
Otherwise, \(\{v_9,v_{10}\} \cap S \neq \varnothing\), and by symmetry \(\forall A \in \{\{v_{12},v_{13}\}, \{v_{17},v_{18}\}, \{v_{20},v_{21}\}\}\), \(A \cap S \neq \varnothing\). Consider the corner \(\{v_1,v_2,v_3\}\): we now know that \(\operatorname{sh}[v_1v_2] \le \max\{\sigma_{35},\sigma_{44}\}\), and similarly for \(\operatorname{sh}[v_2v_3]\). Thus, \(\operatorname{sh}[v_1v_2v_3] \le \max\{\sigma_{345},\sigma_{444}\} = \sigma_{345}\). Suppose \(\operatorname{sh}[v_1v_2v_3] \le \sigma_{444}\), then by symmetry \(\operatorname{sh}[v_5v_6v_7] \le \sigma_{345}\) and we are done. So we can assume \(\exists w \in \{v_1,v_2,v_3\}\) such that \(\operatorname{dom}(w) = 3\), and by Claims 1 and 2, \(w\) is unique. Suppose \(w = v_2\), then by Claim 2 we reach a contradiction; without loss of generality let \(w = v_1\); then \(\operatorname{dom}(v_2) \ge 5\) to distinguish from \(v_1\) because \(\{v_9,v_{10}\} \cap S \neq \varnothing\). If \(\operatorname{dom}(v_3) \ge 5\) then we are done, so we assume \(\operatorname{dom}(v_3) = 4\). If \(\operatorname{dom}(v_2) \ge 6\) we are done, so we assume \(\operatorname{dom}(v_2) = 5\). With symmetry we can also assume that \(\operatorname{dom}(v_6) = 5\), that \((\operatorname{dom}(v_5),\operatorname{dom}(v_7)) \in \{(3,4), (4,3)\}\), and that \(\operatorname{dom}(v_4) = \operatorname{dom}(v_8) = 3\). If \(v_9 \in S\) or \(v_{24} \in S\) then \(v_1\) and \(v_8\) are not distinguished, a contradiction; thus, \(v_9 \notin S\) and \(v_{24} \notin S\), requiring \(v_{10} \in S\). If \(\operatorname{dom}(v_7) = 3\) then by symmetry \(v_{21} \notin S\) and \(v_{22} \notin S\), but we see that \(v_8\) cannot be 3-dominated, a contradiction; therefore \(\operatorname{dom}(v_7) = 4\), meaning \(\operatorname{dom}(v_5) = 3\). By symmetry with \(\{v_9,v_{10},v_{24}\}\), we can assume \(\{v_{16},v_{17},v_{18}\} \cap S = \{v_{18}\}\). If \(v_{21} \in S\) then \(v_{20} \in S\) to distinguish \(v_7\) from \(v_8\), however this results in \(v_6\) and \(v_7\) not being distinguished, a contradiction; thus, we assume \(v_{21} \notin S\). Then to 5-dominate \(v_6\) and 3-dominate \(v_8\) we require \(\{v_{19},v_{20},v_{22},v_{23}\} \subseteq S\). By symmetry, we can also assume that \(v_{13} \notin S\) and \(\{v_{11},v_{12},v_{14},v_{15}\} \subseteq S\). This results in Problem Case 2, which will be handled separately.
To handle the first “diagonal” problem case, we consider the share of \(v_6\). We observe that we need \(\operatorname{dom}(v_{17}) \ge 5\), \(\operatorname{dom}(v_{20}) \ge 4\), and \(\operatorname{dom}(v_{21}) \ge 4\) to distinguish from \(v_5\), \(v_6\), and \(v_7\), respectively. We also see that \(\{v_{18},v_{19}\} \cap D_{4+} \neq \varnothing\) to distinguish from each other. Therefore, \(\operatorname{sh}(v_6) \le \frac{1}{5} + \frac{5}{4} + \frac{3}{3} = \frac{49}{20}\). Additionally, the only detectors adjacent to \(v_6\) other than \(x\) are \(v_{18}\) and \(v_{19}\), which preceding Cases have proven to have share at most \(\frac{38}{15}\). Thus, \(v_6\) has no neighboring detectors with share exceeding \(\frac{38}{15}\) other than \(x\) itself, so it can safely accept \(\frac{38}{15} – \frac{49}{20} = \frac{1}{12}\) discharge from \(x\). Therefore, \(\widehat{sh}(x) \le \frac{31}{12} – \frac{1}{12} = \frac{5}{2} < \frac{38}{15}\) and we are done.
To handle the other “diagonal” problem case, we consider the share of \(v_6\). We observe that we need \(\operatorname{dom}(v_{17}) \ge 4\) and \(\operatorname{dom}(v_{21}) \ge 5\) to distinguish from \(v_7\) and \(v_5\), respectively. We also see that \(|\{v_{18},v_{19},v_{20}\} \cap D_{5+}| \ge 2\) to be distinguished. Therefore, \(\operatorname{sh}(v_6) \le \frac{4}{5} +\frac{3}{4} +\frac{2}{3} = \frac{133}{60}\). Additionally, the only detectors adjacent to \(v_6\) other than \(x\) are \(v_{18}\), \(v_{19}\) and \(v_{20}\), which preceding Cases have proven to have share at most \(\frac{38}{15}\). Thus, \(v_6\) has no neighboring detectors with share exceeding \(\frac{38}{15}\) other than \(x\) itself, so it can accept \(\frac{38}{15} – \frac{133}{60} = \frac{19}{60}\) discharge from \(x\). Therefore, \(\widehat{sh}(x) \le \frac{77}{30} – \frac{19}{60} = \frac{9}{4} < \frac{38}{15}\), completing the diagonal configuration.
Case Wedge. As the last case, we consider when \(x\) is dominated by two neighbors in a “wedge” shape, as in Figure 15. We can assume that \(\{v_1, v_3, v_5, v_6, v_7, v_8\} \cap S = \varnothing\), as otherwise we fall into previous cases.
First, we observe that \(\operatorname{dom}(v_3) \ge 5\) to be distinguished from \(x\), and \(\operatorname{dom}(v_7) \in \{3,4\}\). If \(\operatorname{dom}(v_7) = 4\), then \(\operatorname{dom}(v_6) \ge 5\) is required to be distinguished from \(v_7\); by symmetry, \(\operatorname{dom}(v_8) \ge 5\), so \(\operatorname{sh}(x) \le \frac{3}{5} + \frac{1}{4} + \frac{5}{3} \le \frac{38}{15}\) and we are done. If \(v_7\) is 3-dominated with \(\{v_{21},v_{22}\} \subseteq S\), then we observe that \(\operatorname{dom}(v_8) \ge 6\) to be distinguished from \(v_7\), requiring \(\{v_9,v_{23},v_{24}\} \subseteq S\); thus, \(\operatorname{dom}(v_1) \ge 4\). We also find that \(\operatorname{dom}(v_6) \ge 4\) to be distinguished from \(v_7\). Therefore, \(\operatorname{sh}(x) \le \frac{1}{6} + \frac{1}{5} + \frac{2}{4} + \frac{5}{3} = \frac{38}{15}\) and we are done. By symmetry, we get the same results if \(v_7\) is 3-dominated with \(\{v_{20},v_{21}\} \subseteq S\).
Therefore, we assume \(v_7\) is 3-dominated with \(\{v_{20},v_{22}\} \subseteq S\). We observe that \(\operatorname{dom}(v_8) \ge 4\) to be distinguished from \(v_7\); by symmetry, this is also true for \(v_6\). Suppose that \(v_{19} \notin S\). Then \(\{v_{17},v_{18}\} \subseteq S\) to 4-dominate \(v_6\), and the only way to distinguish \(v_5\) and \(v_6\) is to have \(v_{16} \in S\), so \(\operatorname{dom}(v_5) = 5\) and \(\operatorname{dom}(v_4) \ge 4\). Therefore, \(\operatorname{sh}(x) \le \frac{2}{5} + \frac{3}{4} + \frac{4}{3} = \frac{149}{60} < \frac{38}{15}\) and we are done; otherwise, we assume \(v_{19} \in S\), and by symmetry we also assume \(v_{23} \in S\). Next, suppose that \(\{v_{18},v_{24}\} \cap S = \varnothing\), then \(v_{17} \in S\) and \(v_9 \in S\) to 4-dominate \(v_6\) and \(v_8\), respectively. We observe that we need \(\operatorname{dom}(v_2) \ge 5\) to be distinguished from \(v_1\), and by symmetry \(\operatorname{dom}(v_4) \ge 5\) as well; thus, \(\operatorname{sh}(x) \le \frac{3}{5} + \frac{2}{4} + \frac{4}{3} = \frac{73}{30} < \frac{38}{15}\) and we are done. Otherwise we can assume that \(\{v_{18},v_{24}\} \cap S \neq \varnothing\), and without loss of generality let \(v_{18} \in S\); we now consider the two cases depending on whether \(v_{24}\) is a detector.
If \(v_{24} \notin S\), then \(v_9 \in S\) to 4-dominate \(v_8\) and we observe that \(\operatorname{dom}(v_2) \ge 5\) to be distinguished from \(v_1\). If \(v_{17} \in S\) then \(\operatorname{dom}(v_6) = 5\) and \(\operatorname{dom}(v_5) \ge 4\), resulting in \(\operatorname{sh}(x) \le \frac{3}{5} + \frac{2}{4} + \frac{4}{3} = \frac{73}{30} < \frac{38}{15}\) and we are done; otherwise we assume \(v_{17} \notin S\). If \(\{v_1,v_4,v_5\} \cap D_{4+} \neq \varnothing\) then \(\operatorname{sh}(x) \le \frac{2}{5} + \frac{3}{4} + \frac{4}{3} = \frac{149}{60} < \frac{38}{15}\) and we are done; thus, we can assume that \(\{v_1,v_4,v_5\} \subseteq D_3\). Therefore, \(v_{10} \notin S\) and \(v_{16} \notin S\) because \(v_1\) and \(v_5\) are 3-dominated, respectively. Suppose \(v_{13} \in S\); then \(\{v_{14},v_{15}\} \cap S = \varnothing\) because \(v_4\) is 3-dominated, so we require \(v_{12} \in S\) to 5-dominate \(v_3\). If \(v_{11} \in S\) then \(\operatorname{dom}(v_2) = 6\), resulting in \(\operatorname{sh}(x) \le \frac{1}{6} + \frac{1}{5} + \frac{2}{4} + \frac{5}{3} = \frac{38}{15}\) and we are done; otherwise \(v_{11} \notin S\) and we arrive at Problem Case 1, which will be handled separately. Otherwise, we consider \(v_{13} \notin S\); then \(\{v_{12},v_{14}\} \subseteq S\) to 5-dominate \(v_3\). This requires \(v_{15} \notin S\) because \(v_4\) is 3-dominated, and \(v_{11} \in S\) to 5-dominate \(v_2\); this leads to Problem Case 3, which will be handled separately.
We now consider when \(v_{24} \in S\). Suppose that \(v_9 \in S\); then \(\operatorname{dom}(v_8) = 5\) and \(\operatorname{dom}(v_1) \ge 4\). If \(\operatorname{dom}(v_2) \ge 4\) then \(\operatorname{sh}(x) \le \frac{2}{5} + \frac{3}{4} + \frac{4}{3} = \frac{149}{60} < \frac{38}{15}\) and we are done; otherwise, we assume that \(\operatorname{dom}(v_2) = 3\). Therefore, \(\{v_{10},v_{11},v_{12},v_{13}\} \cap S = \varnothing\), however this results in \(v_1\) and \(v_2\) not being distinguished, a contradiction. Therefore, \(v_9 \notin S\), and by symmetry \(v_{17} \notin S\) as well. By applying the same argumentation, we can also prove that \(v_{10} \notin S\), and by symmetry \(v_{16} \notin S\) as well. Suppose \(v_{13} \in S\). If \(\operatorname{dom}(v_4) = 3\) then \(\{v_{14},v_{15}\} \cap S = \varnothing\), we require \(v_{12} \in S\) to 5-dominate \(v_3\) and \(v_{11} \in S\) to distinguish \(v_2\) and \(v_3\); this leads to Problem Case 2 and will be handled separately. Otherwise, \(\operatorname{dom}(v_4) \ge 4\), and by symmetry \(\operatorname{dom}(v_2) \ge 4\) as well, so \(\operatorname{sh}(x) \le \frac{1}{5} + \frac{4}{4} + \frac{4}{3} = \frac{38}{15}\) and we are done. Therefore, we can assume \(v_{13} \notin S\); then \(\{v_{12},v_{14}\} \subseteq S\) to 5-dominate \(v_3\). If \(\{v_{11},v_{15}\} \subseteq S\) then \(\{v_2,v_4\} \subseteq D_{4+}\), so we are done; otherwise, without loss of generality we assume \(v_{15} \notin S\). If \(v_{11} \in S\) then we arrive at Problem Case 4, otherwise we arrive at Problem Case 5; both of these will be handled separately later.
Wedge Problem Case 1.
To handle Wedge Problem Case 1 configuration, we consider the maximum share of \(v_2\); we will show that \(\operatorname{sh}(v_2) \le \frac{37}{15}\). We observe that \(\operatorname{dom}(v_{13}) \ge 5\) and \(\operatorname{dom}(v_{10}) \ge 4\) to distinguish from \(v_3\) and \(v_1\), respectively. If \(\operatorname{dom}(v_{10}) \ge 5\) then \(\operatorname{sh}(v_2) \le \frac{4}{5} + \frac{5}{3} = \frac{37}{15}\) and we are done; otherwise we assume \(\operatorname{dom}(v_{10}) = 4\). If \(\{v_9,v_{11}\} \cap D_{4+} \neq \varnothing\) then we are done; so we assume \(\{v_9,v_{11}\} \subseteq D_3\). If \(v_{26} \in S\) or \(v_{27} \in S\) to 4-dominate \(v_{10}\), then \(v_{10}\) and \(v_{11}\) are not distinguished, a contradiction. Thus, \(v_{25} \in S\), \(v_{26} \notin S\), and \(v_{27} \notin S\), but we find that \(v_9\) and \(v_{10}\) are not distinguished, a contradiction; therefore, \(\operatorname{sh}(v_2) \le \frac{37}{15}\). Additionally, \(v_2\) is only adjacent to three detectors other than \(x\), \(v_9\), \(v_{12}\), and \(v_{13}\). From previous cases, we know that \(\operatorname{sh}(v_{12}) \le \frac{38}{15}\) and \(\operatorname{sh}(v_{13}) \le \frac{38}{15}\); however, \(\operatorname{sh}(v_9)\) might exceed \(\frac{38}{15}\). Therefore, we conservatively allow \(v_2\) to accept discharge from two sources—\(x\) and potentially \(v_9\)—up to \(\frac{1}{2} \left[ \frac{38}{15} – \frac{37}{15} \right] = \frac{1}{30}\) from each. Thus, \(\widehat{sh}(x) = \frac{77}{30} – \frac{1}{30} = \frac{38}{15}\) and we are done.
Wedge Problem Case 2.
To handle this situation, we look at the share of \(v_2\). We observe that \(\operatorname{sh}[v_{10}v_{11}] \le \sigma_{35}\) to distinguish \(v_{10}\) and \(v_{11}\). Therefore, \(\operatorname{sh}(v_2) \le \frac{3}{5} +\frac{2}{4}+\frac{4}{3} = \frac{73}{30}\). Additionally, \(v_2\) is only adjacent to \(v_{11}\), \(v_{12}\), \(v_{13}\), which the “L” and “Triangle” cases have proven to have share at most \(\frac{38}{15}\). Thus, \(v_2\) has no neighboring detectors with share exceeding \(\frac{38}{15}\) other than \(x\) itself, so it can accept \(\frac{38}{15} – \frac{73}{30} = \frac{1}{10}\) discharge from \(x\). Therefore, \(\widehat{sh}(x) \le \frac{77}{30} – \frac{1}{10} = \frac{37}{15} < \frac{38}{15}\) and we are done.
Wedge Problem Cases 3, 4, and 5.
Consider Problem Cases 3–5, as shown in Figure 16; to handle these cases, we will show that \(\operatorname{sh}(v_4) \le \frac{49}{20}\). We observe that \(\operatorname{dom}(v_{13}) \ge 6\) to distinguish from \(v_3\), \(\operatorname{dom}(v_{17}) \ge 4\) to distinguish from \(v_5\). If \(\{v_{35},v_{36}\} \cap S \neq \varnothing\) then we require \(\operatorname{sh}[v_{15}v_{16}] \le \max \left\{ \sigma_{36},\sigma_{45} \right\} = \sigma_{36}\) to distinguish \(v_{15}\) from \(v_{16}\), so \(\operatorname{sh}(v_4) \le \frac{49}{20}\) and we are done; thus, we assume \(\{v_{35},v_{36}\} \cap S = \varnothing\), meaning \(\operatorname{dom}(v_{16}) = 3\), so \(\operatorname{dom}(v_{15}) \ge 4\). If \(\operatorname{dom}(v_{14}) \ge 4\) then we will be done, so we assume \(\operatorname{dom}(v_{14}) = 3\). If \(v_{30} \notin S\) or \(v_{33} \in S\) then we contradict that \(\operatorname{dom}(v_{13}) \ge 6\), so we assume \(v_{30} \in S\) and \(v_{33} \notin S\). Thus, we require \(\{v_{32},v_{34}\} \subseteq S\) to 4-dominate \(v_{15}\), and \(v_{31} \notin S\) because \(\operatorname{dom}(v_{14}) = 3\). We see that \(v_{14}\) and \(v_{15}\) are not distinguished, a contradiction. Therefore, we have proven that \(\operatorname{sh}(x_4) \le \frac{49}{20}\). Additionally, the only detector adjacent to \(v_4\) other than \(x\) is \(v_{14}\), which previous cases have shown to have share no more than \(\frac{38}{15}\); so \(v_4\) can accept \(\frac{38}{15} – \frac{49}{20} = \frac{1}{12}\) discharge from \(x\). Consider Problem Cases 3 and 4: \(\operatorname{sh}(x) \le \max \left\{ \frac{157}{60}, \frac{77}{30} \right\} = \frac{157}{60}\). Then \(\widehat{sh}(x) \le \frac{157}{60} – \frac{1}{12} = \frac{38}{15}\) and we are done. Consider Problem Case 5: \(\operatorname{sh}(x) = \frac{27}{10}\). By symmetry, we can also discharge up to \(\frac{1}{12}\) from \(x\) into \(v_2\), so \(\widehat{sh}(x) \le \frac{27}{10} – 2 \times \frac{1}{12} = \frac{38}{15}\), completing the proof of Theorem 4.1. ◻
Theorem 4.2. Let \(S \subseteq V(G)\) be a RED:LD set on \(\textrm{K}\). Then, the average share of all vertices in \(S\) is at most \(\frac{11}{3}\).
Proof. Let \(S \subseteq V(G)\) be a RED:LD set on \(\textrm{K}\), let the notations \(sh\), \(dom\), and \(k\)-dominated implicitly use \(S\), and let a vertex pair being distinguished denote satisfying the relevant pair property of Theorem 1.2. Let \(x \in S\) be a detector vertex; Theorem 1.2 yields that \(|N[x] \cap S| \ge 2\). There are two non-isomorphic ways to 2-dominate \(x\), either “vertically” or “diagonally.”
Case Vertical. Consider the “vertical” configuration given in Figure 19. We begin by examining the vertex pair \((v_2,v_3)\). If \(|\{v_2,v_3\} \cap S| = 2\) then \(\{x,v_1,v_2,v_3\} \subseteq D_{4+}\), so \(\operatorname{sh}(x) \le \frac{4}{4} + \frac{5}{2} < \frac{11}{3}\) and we are done. Next, suppose \(|\{v_2,v_3\} \cap S| = 1\), then \(\{x,v_1,v_2,v_3\} \subseteq D_{3+}\). If \(\{v_7,v_8\} \cap S \neq \varnothing\) then \(\operatorname{sh}(x) \le \frac{2}{4} + \frac{2}{3} + \frac{5}{2} = \frac{11}{3}\) and we are done, so we assume \(\{v_7,v_8\} \cap S = \varnothing\). We observe that if \(\{v_7,v_8\} \subseteq D_2\) then they will not be distinguished, so \(\operatorname{dom}(v_7) \ge 3\) or \(\operatorname{dom}(v_8) \ge 3\) and we are done. Lastly, suppose \(|\{v_2,v_3\} \cap S| = 0\); by symmetry we can assume that \(\{v_7,v_8\} \cap S = \varnothing\) as well. We require \(\operatorname{sh}[v_2v_3] \le \max\{\sigma_{33},\sigma_{24}\}\) to be distinguished; by symmetry, this is also true for \(\operatorname{sh}[v_7v_8]\). If \(\operatorname{dom}(v_2) = 2\), then \(\{x,v_1\} \subseteq D_{3+}\) and \(\operatorname{dom}(v_3) \ge 4\) to distinguish from \(v_2\); thus \(\operatorname{sh}(x) \le \sigma_{24} + \sigma_{24} + \sigma_{33} + \sigma_{222} = \frac{11}{3}\) and we are done. Similarly, we are also done if \(\operatorname{dom}(v_3) = 2\). Therefore, we can assume \(\{v_2,v_3,v_7,v_8\} \subseteq D_{3+}\). If \(\operatorname{dom}(x) \ge 3\) we are done, so \(\{v_4,v_5,v_6\} \cap S = \varnothing\). If \(\{v_4,v_5,v_6\} \cap D_{3+} \neq \varnothing\) then we will be done, so we assume \(\{v_4,v_5,v_6\} \subseteq D_2\). Vertex \(v_5\) must be 2-dominated by exactly one of \(v_{16}\), \(v_{17}\), or \(v_{18}\). If \(v_{16} \in S\) or \(v_{17} \in S\) then \(v_4\) and \(v_5\) will not be distinguished, a contradiction; otherwise \(v_{18} \in S\), but then \(v_5\) and \(v_6\) are not distinguished, a contradiction.
Case Diagonal. Consider the other case for 2-dominating \(x\), the “diagonal” configuration show in Figure 20. We can assume that \(\{v_1,v_3,v_5,v_7\} \cap S = \varnothing\), as otherwise we fall into the previous case.
We observe that \(\operatorname{sh}[v_1v_3] \le \max\{\sigma_{33},\sigma_{24}\}\) to be distinguished. Suppose \(\operatorname{dom}(v_1) = 2\), then \(\operatorname{dom}(v_3) \ge 4\) to be distinguished. Additionally, \(\{x,v_2\} \subseteq D_{3+}\) to be distinguished from \(v_1\). If \(v_6 \in S\) then \(\operatorname{sh}[v_5v_7] \le \sigma_{24}\) and we are done; so we assume \(v_6 \notin S\). Suppose \(v_8 \in S\), then \(\operatorname{dom}(v_7) \ge 4\) to distinguish from \(v_1\) and we are done; so we assume \(v_8 \notin S\). Thus, \(v_4 \in S\) to 3-dominate \(x\). If \(\{v_4,v_5\} \subseteq D_2\) then they are not distinguished, so \(\operatorname{sh}[v_4v_5] \le \sigma_{23}\) and we are done. Therefore, we can assume that \(\{v_1,v_3\} \subseteq D_{3+}\). If \(v_6 \in S\) then we can assume \(\{v_5,v_7\} \subseteq D_{3+}\), and \(\operatorname{dom}(x) \ge 3\), so we are done; thus, we assume \(v_6 \notin S\). Next, we consider the vertex pair \((v_4,v_8)\). Suppose \(\{v_4,v_8\} \subseteq S\). If \(\{v_4,v_5\} \subseteq D_2\) they will not be distinguished, so \(\operatorname{sh}[v_4v_5] \le \sigma_{23}\), and by symmetry \(\operatorname{sh}[v_7v_8] \le \sigma_{23}\), and we are done. Next, we assume \(|\{v_4,v_8\} \cap S| = 1\), and without loss of generality let \(v_4 \in S\). We see that \(\operatorname{sh}[v_4v_5] \le \sigma_{23}\) to be distinguished. If \(\{v_6,v_7,v_8\} \cap D_{3+} \neq \varnothing\) we will be done, so we assume \(\{v_6,v_7,v_8\} \subseteq D_2\). Any way to 2-dominate \(v_7\) will result in either \((v_7,v_8)\) or \((v_6,v_7)\) not being distinguished, a contradiction.
Finally, we assume that \(\{v_4,v_8\} \cap S = \varnothing\). Suppose \(v_{17} \in S\) then \(\operatorname{dom}(v_4) \ge 3\) and \(\operatorname{dom}(v_6) \ge 3\) to distinguish from \(v_5\). If \(\operatorname{dom}(v_5) \ge 3\) we are done, so we assume \(\operatorname{dom}(v_5) = 2\), so \(\{v_{16},v_{17}\} \cap S = \varnothing\). Thus, \(\operatorname{dom}(v_4) \ge 4\) and \(\operatorname{dom}(v_6) \ge 4\) to distinguish from \(v_5\), and we are done; so we assume \(v_{17} \notin S\), and by symmetry \(v_{21} \notin S\). If \(\operatorname{dom}(v_5) \ge 3\), then \(\{v_{16},v_{18}\} \subseteq S\); we require \(\operatorname{dom}(v_4) \ge 3\) and \(\operatorname{dom}(v_6) \ge 3\) to distinguish from \(v_5\), and we are done, so we can assume \(\operatorname{dom}(v_5) = 2\), and by symmetry \(\operatorname{dom}(v_7) = 2\). Suppose \(v_{16} \in S\), then \(v_{18} \notin S\). We require \(\operatorname{dom}(v_4) \ge 4\) to distinguish from \(v_5\). If \(v_{22} \in S\) as well, then \(v_{20} \notin S\) and we find that \(\operatorname{dom}(v_8) \ge 4\) to distinguish from \(v_7\), and we are done; thus, we assume \(v_{22} \notin S\), so \(v_{20} \in S\) to 2-dominate \(v_7\). We find that \(v_6\) and \(v_7\) are not distinguished, a contradiction; therefore, we assume \(v_{16} \notin S\), and by symmetry \(v_{22} \notin S\). Thus, \(\{v_{18}, v_{20}\} \subseteq S\), and \(\operatorname{dom}(v_6) = 4\) with \(v_{19} \in S\) to distinguish from \(v_5\). Suppose \(\{v_{12},v_{13}\} \cap S \neq \varnothing\); then \(\operatorname{dom}(v_2) \ge 3\). If \(\operatorname{dom}(v_2) \ge 4\) we are done, so we assume \(\operatorname{dom}(v_2) = 3\); thus, \(\{v_9,v_{10},v_{11}\} \cap S = \varnothing\). We require \(v_{24} \in S\) to 3-dominate \(v_1\) and \(\operatorname{dom}(v_8) \ge 3\) to distinguish from \(v_1\), so we are done. Therefore, we can assume \(\{v_{12},v_{13}\} \cap S = \varnothing\). Then \(v_{14} \in S\) to 3-dominate \(v_3\) and \(\operatorname{dom}(v_4) \ge 3\) to distinguish from \(v_3\), and by symmetry we find \(\operatorname{dom}(v_8) \ge 3\) as well, completing the proof. ◻
We have now explored upper and lower bounds for the optimal densities of three types of fault-tolerant LD sets—RED:LD, DET:LD, and ERR:LD—on the infinite king grid. Table 1 summarizes the bounds proven in this paper, as well as the tight bound for the base (non-fault-tolerant) LD set proven by Honkala and Laihonen [4] for comparison.
| Parameter | Bounds | Sources |
|---|---|---|
| LD(K) | \(\frac{1}{5}\) | [4] |
| RED:LD(K) | \(\left[\frac{3}{11}, \frac{5}{16}\right]\) | Theorem 4.2 and Figure 2 (b) |
| DET:LD(K) | \(\left[\frac{3}{11}, \frac{3}{8}\right]\) | Theorem 4.2 and Figure 2 (c) |
| ERR:LD(K) | \(\left[\frac{15}{38}, \frac{7}{16}\right]\) | Theorem 4.1 and Figure 2 (d) |
We note that the lowerbound of \(\frac{3}{11}\) for DET:LD(K) reuses the result of Theorem 4.2 for RED:LD(K) due to the fact that every DET:LD set is also a RED:LD set, implying \(\textrm{RED:LD}(G) \le \textrm{DET:LD}(G)\) for any graph \(G\). This fact can be verified by observing that the conditions of Theorem 1.3 imply the conditions of Theorem 1.2.
By computer-assisted search, we believe the same discharging technique used in the proofs of Theorems 4.1 and 4.2 can be used to prove the following stronger bound on DET:LD(K); however, we have not constructed a formal proof of this fact and leave it as future work.
Conjecture 5.1. \(\frac{15}{44} \le \textrm{DET:LD}(\textrm{K})\).
Even using the same discharging technique introduced in this paper, it may be possible to strengthen these lowerbounds in future research. For example, our discharging argument only requires \(k(v)\) to be an upperbound on the number of neighbors of \(v\) which simultaneously have share exceeding \(t\). However, our current applications of this technique use a conservative upper bound by expanding each neighbor of \(v\) separately rather than simultaneously. Essentially, we have used \(k'(v) = |\{ u \in N(v) \cap S : \max \operatorname{sh}(u) > t\}|\) rather than the possibly tighter \(k(v) = \max |\{u \in N(v) \cap S : \operatorname{sh}(u) > t\}| \le k'(v)\) presented in Algorithm 1. This dramatically reduces casing complexity, but may result in a worse lowerbound than otherwise could be proven using this technique.