On \(k\)-limited domination: complexity and Cartesian products
June 21, 2026
Abstract
A dominating set is called \(k\)-limited if every vertex in the set has at most \(k\) neighbors outside it. The minimum cardinality of a \(k\)-limited dominating set is the \(k\)-limited domination number, denoted by \(\gamma_k^{\mathrm{L}}(G)\). We prove that, for every fixed integer \(k\ge 2\), deciding whether a graph admits a \(k\)-limited dominating set of size at most \(\ell\) is \(\mathsf{NP}\)-complete. In addition, a systematic study of \(k\)-limited domination in Cartesian products is initiated. In particular, we establish general lower and upper bounds for \(\gamma_k^{\mathrm{L}}(G\square H)\), show that both are sharp, and derive exact values for several natural families of graph products. Among others, we obtain exact results for rook graphs, Cartesian products of \(k\)-coronas, certain grid graphs, and several cases involving prisms and hypercubes.
Keywords: domination, \(k\)-limited domination, Cartesian products, hypercubes
1 Introduction↩︎
A dominating set of a graph \(G\) is a set of vertices such that every vertex outside the set has a neighbor in it, and the minimum size of such a set is the domination number \(\gamma(G)\). Over the years, domination has been studied from many different perspectives and on many graph classes; we refer to the monographs [1]–[3] for background and further references. At the same time, several central open problems in domination theory remain unresolved, among them Vizing’s conjecture on domination in Cartesian products [4], and the problem of determining the domination number of hypercubes, which is known exactly only in a limited number of cases [5]–[7].
Recently, in [8], the notion of \(k\)-limited domination was introduced as a natural variant of classical domination. Many previously studied domination variants impose additional requirements on vertices outside the dominating set; for instance, in \(k\)-domination every vertex outside the set must have at least \(k\) neighbors in it [9], while in \([1,k]\)-domination every vertex outside the set must have at least one and at most \(k\) neighbors in it [10], [11]. By contrast, \(k\)-limited domination places the restriction on the vertices inside the dominating set. In the usual domination model, one seeks a dominating set of minimum cardinality, but no restriction is imposed on how many vertices outside the set may be assigned to the same dominator. In many situations, however, this is unrealistic: if the selected vertices represent facilities, service providers, or communication nodes, for example, then each of them can typically handle only a limited number of external users. This leads to the requirement that every chosen vertex have at most \(k\) neighbors outside the dominating set. In this way, \(k\)-limited domination preserves the covering aspect of classical domination while adding a local restriction on the number of external vertices assigned to each dominating vertex.
Formally, as introduced in [8], let \(G\) be a graph and let \(k\) be an integer such that \(0\le k\le \Delta(G)\). A set \(D\subseteq V(G)\) is called a \(k\)-limited dominating set if \(D\) is a dominating set of \(G\) and \[|N_G(u)\setminus D|\le k \qquad\text{for every }u\in D.\] The minimum cardinality of a \(k\)-limited dominating set of \(G\) is the \(k\)-limited domination number of \(G\), denoted by \(\gamma_k^{\mathrm L}(G)\). We will refer to the above local degree condition as the \(k\)-limited constraint. In [8], the parameter was defined in the range \(0\le k\le \Delta(G)\), where the two extreme cases are essentially trivial: if \(k=0\), then every vertex of a \(k\)-limited dominating set has no neighbors outside the set, which forces \(\gamma^{\mathrm L}_0(G)=|V(G)|\), while for \(k=\Delta(G)\) one recovers the classical domination number. Thus, for graphs with \(\Delta(G)\ge 2\), the genuinely interesting range is \(1\le k\le \Delta(G)-1\). As we shall see in Section 2, however, the definition extends naturally to all integers \(k\ge 0\); in particular, for every \(k\ge \Delta(G)\) one has \(\gamma_k^{\mathrm L}(G)=\gamma(G)\). This extension will be convenient in our study of Cartesian products.
The initial study in [8] laid the foundations for the systematic investigation of this parameter. It established general bounds on \(\gamma_k^{\mathrm L}(G)\) and determined exact values for several basic graph families. It also showed that, for efficient graphs, that is, graphs admitting a dominating set in which every vertex is dominated exactly once, the parameter coincides with the classical domination number once \(k\) is sufficiently large, and that under suitable structural assumptions one can derive improved upper bounds in terms of \(\gamma(G)\). In addition, strong links with other domination-type parameters were uncovered. In particular, a close connection with \((1,t)\)-domination was established, where every vertex outside the dominating set must have at least one neighbor in the set, while every vertex inside the set must have at least \(t\) neighbors in the set [12], [13]. For connected \(d\)-regular graphs and \(1\le k<d\), this relation takes the precise form \(\gamma_k^{\mathrm L}(G)=\gamma_{1,d-k}(G)\). Finally, the case \(k=1\) was studied in more detail via its connection with the packing number, leading to further structural results and characterizations.
The present paper continues this line of research in two directions. First, we investigate the algorithmic complexity of the parameter and prove in Section 3 that \(k\)-Limited Dominating Set is \(\mathsf{NP}\)-complete for every fixed integer \(k\ge 2\). Second, we initiate a systematic study of \(k\)-limited domination in Cartesian products. Before turning to these two topics, in Section 2 we collect the definitions and auxiliary results needed later. The Cartesian product aspect is treated in Section 4, where we establish general bounds for \(\gamma_k^{\mathrm L}(G\square H)\), show that both are sharp, and derive exact values for several natural families of products, including rook graphs, Cartesian products of \(k\)-coronas, certain grid graphs, and selected cases involving prisms and hypercubes. We conclude in Section 5 with several open problems suggested by our results, particularly in the case of hypercubes.
2 Preliminaries↩︎
Let \(G\) be a finite simple graph. Its vertex set and edge set are denoted by \(V(G)\) and \(E(G)\), respectively, and its order by \(n(G)=|V(G)|\). For a vertex \(v\in V(G)\), we write \(N_G(v)\) for the open neighborhood of \(v\) and \(\deg_G(v)\) for its degree. The maximum degree of \(G\) is denoted by \(\Delta(G)\). When the graph is clear from the context, we omit the subscript. Also, for ease of notation, we write \([k]=\{1,\dots,k\}\) for every positive integer \(k\).
A set \(D\subseteq V(G)\) is a dominating set of \(G\) if every vertex of \(V(G)\setminus D\) has a neighbor in \(D\). The minimum cardinality of a dominating set of \(G\) is the domination number of \(G\), denoted by \(\gamma(G)\). Let \(k\) be an integer such that \(0\le k\le \Delta(G)\). A dominating set \(D\subseteq V(G)\) is called a \(k\)-limited dominating set if \(|N_G(u)\setminus D|\le k\) for every \(u\in D\). The minimum cardinality of a \(k\)-limited dominating set of \(G\) is the \(k\)-limited domination number of \(G\), denoted by \(\gamma_k^{\mathrm L}(G)\), [8].
If \(k=0\), then every vertex of a \(k\)-limited dominating set has no neighbors outside the set, and hence \(\gamma^{\mathrm L}_0(G)=|V(G)|\). On the other hand, if \(k=\Delta(G)\), then every dominating set of \(G\) is automatically \(k\)-limited, and therefore \(\gamma_k^{\mathrm L}(G)=\gamma(G)\). Moreover, if \(D\) is a \(k\)-limited dominating set of \(G\), then it is also a \((k+1)\)-limited dominating set of \(G\). Indeed, for every \(u\in D\), the inequality \(|N_G(u)\setminus D|\le k\) immediately implies \(|N_G(u)\setminus D|\le k+1\). Therefore \(\gamma^{\mathrm L}_{k+1}(G)\le \gamma^{\mathrm L}_k(G)\) for every \(0\le k<\Delta(G)\). Consequently, \(\gamma_k^{\mathrm L}(G)\) admits a natural extension to all integers \(k\ge 0\), and in particular \(\gamma_k^{\mathrm L}(G)=\gamma(G)\) for every \(k\ge \Delta(G)\). This also explains why in [8] the focus was on the nontrivial range \(1\le k\le \Delta(G)-1\).
Observation 1. Let \(G\) be a graph. Then \[\gamma^{\mathrm L}_0(G)\ge \gamma^{\mathrm L}_1(G)\ge \gamma^{\mathrm L}_2(G)\ge \cdots \ge \gamma^{\mathrm L}_{\Delta(G)}(G)=\gamma(G).\] Moreover, \(\gamma_k^{\mathrm L}(G)=\gamma(G)\) for every \(k\ge \Delta(G)\).
The following general bounds for \(k\)-limited domination were proved in [8].
Theorem 2. [8] Let \(G\) be a connected graph of order \(n\geq 3\), and \(1\leq k < \Delta(G)\). Then \[\max\left\{\gamma(G),\;\left\lceil \frac{n}{k+1} \right\rceil\right\} \leq \gamma_k^{\mathrm L}(G) \leq n-k.\]
Several graph families were also considered in [8]. In what follows, we will use the \(k\)-limited domination numbers of paths and complete graphs.
Proposition 3. [8] Let \(k\) be a positive integer. Then the following holds.
For every \(n\geq 3\) we have \(\gamma_1^{\mathrm L}(P_n) = \lceil\frac{n}{2}\rceil\).
For every \(n\geq 3\) and \(k\) such that \(1\leq k<n\) we have \(\gamma_k^{\mathrm L}(K_n) = n - k\).
As already mentioned, one of the main goals of this paper is to initiate a systematic study of \(k\)-limited domination in Cartesian products. We therefore conclude this section by recalling the following definition. The Cartesian product \(G \square H\) has vertex set \(V(G \square H) = V(G) \times V(H)\), where two vertices \((g,h)\) and \((g',h')\) are adjacent if and only if either \(g=g'\) and \(hh' \in E(H)\), or \(h=h'\) and \(gg' \in E(G)\). As usual, we write \(n(G)=|V(G)|\) and \(n(H)=|V(H)|\) for the orders of the respective factors.
3 Computational Complexity↩︎
In this section we investigate the algorithmic side of \(k\)-limited domination. Although the notion is closely related to classical domination, the extra local restriction on the dominating vertices does not lead to an easier decision problem. As announced in the introduction, we prove that the \(k\)-Limited Dominating Set problem, whose decision version is given in Table 1, is \(\mathsf{NP}\)-complete for every fixed integer \(k\ge 2\). Throughout this section we work with an arbitrarily chosen integer \(k\ge 2\), while \(\ell\) is part of the input.
| Instance: A graph \(G\) and a positive integer \(\ell\). |
|---|
| Question: Does \(G\) admit a \(k\)-limited dominating set \(D\) with \(|D|\le \ell\)? |
Given a set \(D\subseteq V(G)\), one can check in polynomial time whether \(D\) dominates \(G\) and whether every vertex \(u\in D\) satisfies the \(k\)-limited constraint \(|N_G(u)\setminus D|\le k\). Hence, \(k\)-Limited Dominating set belongs to \(\mathsf{NP}\).
To prove \(\mathsf{NP}\)-completeness, we give a polynomial reduction from the classical Dominating Set problem, formulated in Table 2, which is known to be \(\mathsf{NP}\)-complete [14].
| Instance: A graph \(G\) and a positive integer \(\ell\). |
|---|
| Question: Does \(G\) have a dominating set \(D\) with \(|D|\le \ell\)? |
Let \(G\) be an arbitrary graph of order \(n\) with vertex set \(V(G)=\{v_1,\dots,v_n\}\) and \(m=|E(G)|\). From \(G\) we construct a graph \(G'\) by replacing each edge with a constant-size gadget \(S\) that enforces a fixed minimum contribution in any \(k\)-limited dominating set.
The gadget \(S\) is obtained from the complete graph \(K_k\) on vertex set \(\{c,d_1,\dots,d_{k-1}\}\) by adding two new vertices \(a\) and \(b\) together with the edges \(ab\) and \(bc\). Furthermore, for each \(t\in[k]\) we add two new vertices \(x_t\) and \(y_t\) and the edges \(bx_t\) and \(x_ty_t\). No other edges are added. In particular, \(|V(S)|=3k+2\). Observe that the encircled subgraph \(S^{ij}\) in Figure 1 is isomorphic to \(S\).
We now define \(G'\). For each edge \(v_iv_j\in E(G)\) we subdivide \(v_iv_j\) once by a new vertex \(c^{ij}\), that is, we delete \(v_iv_j\) and add the edges \(v_ic^{ij}\) and \(c^{ij}v_j\). Next, for each edge \(v_iv_j\in E(G)\) we take a copy \(S^{ij}\) of \(S\) and identify its vertex corresponding to \(c\) with the subdivision vertex \(c^{ij}\). We denote the remaining vertices of \(S^{ij}\) by \(a^{ij}\), \(b^{ij}\), \(d^{ij}_1,\dots,d^{ij}_{k-1}\) and \(x^{ij}_t,y^{ij}_t\) for \(t\in[k]\), see Figure 1. Denote the resulting graph by \(G'\).
Since the construction only replaces edges of \(G\), each vertex of \(G\) naturally remains a vertex of \(G'\). Thus we regard \(V(G)\) as a subset of \(V(G')\), and refer to its elements as the original vertices of \(G'\). Clearly, \(|V(G')|=n+(3k+2)m\), and the construction can be carried out in polynomial time.
The next proposition states the correctness of the reduction.
Proposition 4. Let \(k\ge 2\) be a fixed integer, and let \(G'\) be constructed from \(G\) as described above. Then \(G\) has a dominating set of size at most \(\ell\) if and only if \(G'\) has a \(k\)-limited dominating set of size at most \(\ell+(k+2)m\).
Proof. Assume that \(G\) has a dominating set \(D\subseteq V(G)\) with \(|D|\le \ell\). We define a set \(D'\subseteq V(G')\) by taking \(D\) together with a fixed selection of vertices from each gadget. More precisely, for every edge \(v_iv_j\in E(G)\) we add to \(D'\) the vertices \(b^{ij}\) and \(x^{ij}_t\) for all \(t\in[k]\). In addition, we include \(c^{ij}\) whenever \(v_i\in D\) or \(v_j\in D\), and otherwise we include \(d^{ij}_1\). Formally, \[D' \;=\; D \;\cup\!\!\!\bigcup_{v_iv_j\in E(G)}\!\!\!\Bigl(\{b^{ij}\}\cup\{x^{ij}_t:t\in[k]\}\cup Z^{ij}\Bigr),\] where \(Z^{ij}=\{c^{ij}\}\) if \(v_i\in D\) or \(v_j\in D\), and \(Z^{ij}=\{d^{ij}_1\}\) otherwise. Each gadget contributes exactly \(k+2\) vertices, and therefore \[|D'|=|D|+(k+2)m\le \ell+(k+2)m.\] We claim that \(D'\) is a \(k\)-limited dominating set of \(G'\).
Fix an edge \(v_iv_j\in E(G)\) and consider the corresponding copy \(S^{ij}\). For every \(t\in[k]\), the vertex \(y^{ij}_t\) is adjacent to \(x^{ij}_t\in D'\), and \(a^{ij}\) is adjacent to \(b^{ij}\in D'\). Moreover, since \(\{c^{ij},d^{ij}_1,\dots,d^{ij}_{k-1}\}\) induces a clique and we ensured that at least one of \(c^{ij}\) and \(d^{ij}_1\) belongs to \(D'\), all other vertices in this clique are dominated as well. Thus every vertex inside every gadget is dominated. Now let \(v_i\) be an original vertex of \(G'\) with \(v_i\notin D'\). Since \(D\subseteq D'\), the assumption \(v_i\notin D'\) immediately implies \(v_i\notin D\). Since \(D\) is a dominating set of \(G\), there exists a neighbor \(v_j\in D\) such that \(v_iv_j\in E(G)\). Consider the subdivision vertex \(c^{ij}\) corresponding to the edge \(v_iv_j\). By the definition of \(D'\), \(v_j\in D\) implies that \(c^{ij}\in D'\). As \(v_i\) is adjacent to \(c^{ij}\) in \(G'\), it follows that \(v_i\) is dominated in \(G'\). This shows that \(D'\) is a dominating set of \(G'\).
It remains to verify the \(k\)-limited constraint. Let \(u\in D'\). If \(u\) is an original vertex \(v_i\in D\), then all its neighbors in \(G'\) are subdivision vertices \(c^{ij}\), and each such \(c^{ij}\) is included in \(D'\) by construction, hence \(|N_{G'}(u)\setminus D'|=0\). If \(u\in D'\cap V(S^{ij})\) is a gadget vertex different from \(c^{ij}\), then \(u\in\{x^{ij}_t,b^{ij},d^{ij}_1\}\). In the first two cases, \(u\) has at most two neighbors outside \(D'\). In the third case, when \(u=d^{ij}_1\), we have \(\deg_{G'}(u)=k-1\). Thus \(|N_{G'}(u)\setminus D'|\le k\) holds for all such vertices. Finally, consider a subdivision vertex \(c^{ij}\in D'\). It has degree \(k+2\), and it is adjacent to \(b^{ij}\in D'\) and to at least one of \(v_i,v_j\in D\subseteq D'\) by the definition of \(D'\). Therefore \(c^{ij}\) has at most \(k\) neighbors outside \(D'\). This completes the proof that \(D'\) is a \(k\)-limited dominating set of size at most \(\ell+(k+2)m\).
Conversely, let \(D'\) be a \(k\)-limited dominating set of \(G'\) with \(|D'|\le \ell+(k+2)m\). Define \(D_0= D'\cap V(G)\), that is, the set of original vertices of \(G\) that belong to \(D'\).
We first show that gadgets are designed so that each of them forces at least \(k+2\) vertices in any \(k\)-limited dominating set of \(G'\). Fix \(v_iv_j\in E(G)\) and consider \(S^{ij}\). For each \(t\in[k]\), the vertex \(y^{ij}_t\) has the unique neighbor \(x^{ij}_t\), hence \(\{x^{ij}_t,y^{ij}_t\}\cap D'\neq\emptyset\), contributing at least \(k\) vertices from \(V(S^{ij})\). Also, \(a^{ij}\) has the unique neighbor \(b^{ij}\), so \(\{a^{ij},b^{ij}\}\cap D'\neq\emptyset\), contributing one more vertex. Finally, every \(d^{ij}_s\), where \(s\in [k-1]\), has neighbors only within the clique on \(\{c^{ij},d^{ij}_1,\dots,d^{ij}_{k-1}\}\), so domination of \(\{d^{ij}_1,\dots,d^{ij}_{k-1}\}\) forces \(D'\) to contain at least one vertex from this clique. Therefore, for every edge \(v_iv_j\in E(G)\), the corresponding copy \(S^{ij}\) satisfies \(|D'\cap V(S^{ij})|\ge k+2\).
Applying this bound to each of the \(m\) gadgets and summing the resulting inequalities yields \[|D_0| =|D'|-\sum_{v_iv_j\in E(G)}|D'\cap V(S^{ij})| \le |D'|-(k+2)m \le \ell.\] Thus, \(|D_0|\le \ell\). If \(D_0\), seen as a subset of \(G\), already dominates \(G\), then we are done.
Assume therefore that \(D_0\) is not a dominating set of \(G\). We will show that \(D'\) can be modified iteratively into a \(k\)-limited dominating set \(\widehat{D}\) of \(G'\) with \(|\widehat{D}|\le |D'|\) such that the set of original vertices of \(G'\) contained in \(\widehat{D}\) forms a dominating set of \(G\). Let \[W=\{\,v\in V(G)\setminus D_0:\;N_G(v)\cap D_0=\emptyset\,\}\] be the set of vertices not dominated by \(D_0\) in \(G\). Since \(D_0\) is not a dominating set of \(G\), the set \(W\) is nonempty. Choose a vertex \(v_i\in W\).
As \(D'\) dominates \(G'\), the original vertex \(v_i\) has a neighbor in \(D'\). By construction of \(G'\), the neighbors of \(v_i\) in \(G'\) are precisely the subdivision vertices \(c^{ir}\) corresponding to edges \(v_iv_r\in E(G)\). Hence there exists a neighbor \(v_j\in N_G(v_i)\) such that \(c^{ij}\in D'\). Since \(v_i\in W\), no neighbor of \(v_i\) in \(G\) belongs to \(D_0\). In particular, the vertex \(v_j\) chosen above does not belong to \(D_0\). As \(v_j\) is an original vertex and \(D_0=D'\cap V(G)\), it follows that \(v_j\notin D'\).
We already know that \(|D'\cap V(S^{ij})|\ge k+2\). We now show that under the additional assumptions \(c^{ij}\in D'\) and \(v_i,v_j\notin D'\), one more gadget vertex is forced to be in \(D'\), that is, \(|D'\cap V(S^{ij})|\ge k+3\). For each \(t\in[k]\), the leaf \(y^{ij}_t\) must be dominated by \(x^{ij}_t\) or by itself, so \(\{x^{ij}_t,y^{ij}_t\}\cap D'\neq\emptyset\), yielding at least \(k\) vertices of \(D'\) in \(V(S^{ij})\). Moreover, since \(a^{ij}\) is adjacent only to \(b^{ij}\), we have \(\{a^{ij},b^{ij}\}\cap D'\neq\emptyset\). It remains to show that \(D'\) contains at least one vertex among \(d^{ij}_1,\dots,d^{ij}_{k-1}\). Recall that \(c^{ij}\in D'\) and \(v_i,v_j\notin D'\). Since \(\deg_{G'}(c^{ij})=k+2\), the vertex \(c^{ij}\) already has two neighbors outside \(D'\), namely \(v_i\) and \(v_j\). As \(D'\) is \(k\)-limited, at least two vertices from \(\{b^{ij},d^{ij}_1,\dots,d^{ij}_{k-1}\}\) must belong to \(D'\), which further implies that at least one of \(d^{ij}_1,\dots,d^{ij}_{k-1}\) belongs to \(D'\). Therefore \(|D'\cap V(S^{ij})|\ge k+3\).
We now adjust \(D'\) locally around \(v_i\) to obtain another \(k\)-limited dominating set \(D''\) in which \(v_i\) is selected. For each edge \(v_iv_r\in E(G)\), let \[C^{ir}=\{c^{ir},\, b^{ir}\}\cup\{x^{ir}_t:\;t\in[k]\}.\] Then \(|C^{ir}|=k+2\), and \(C^{ir}\) dominates \(S^{ir}\), see Figure 2. Now define \[D'' = \Bigl(D'\setminus \bigcup_{v_iv_r\in E(G)} (D'\cap V(S^{ir}))\Bigr)\;\cup\;\{v_i\}\;\cup\;\bigcup_{v_iv_r\in E(G)} C^{ir}.\] In other words, we replace the part of \(D'\) inside each gadget incident with \(v_i\) by the corresponding set \(C^{ir}\), and then add \(v_i\).
We first show that \(|D''|\le |D'|\). For every neighbor \(v_r\) of \(v_i\), the lower bound proved above gives \(|D'\cap V(S^{ir})|\ge k+2=|C^{ir}|\), so replacing \(D'\cap V(S^{ir})\) by \(C^{ir}\) does not increase the size. Moreover, for the specific neighbor \(v_j\) chosen above we have \(|D'\cap V(S^{ij})|\ge k+3,\) and hence on the gadget \(S^{ij}\) the replacement decreases the size by at least \(1\). This compensates for the addition of \(v_i\), and therefore \(|D''|\le |D'|\).
Next, we verify that \(D''\) is still a \(k\)-limited dominating set of \(G'\). First, domination is preserved. Each modified gadget \(S^{ir}\) is dominated by \(C^{ir}\), and since \(c^{ir}\in C^{ir}\), both original vertices \(v_i\) and \(v_r\) remain dominated. All other vertices of \(V(G')\setminus D''\) lie outside the modified gadgets, and their neighborhoods are unchanged. Hence these vertices remain dominated as well. It remains to check that the \(k\)-limited constraint holds for every \(u\in D''\). The newly added original vertex \(v_i\) has no neighbors outside \(D''\), since all its neighbors in \(G'\) are subdivision vertices \(c^{ir}\) and all of them belong to \(D''\) by construction. Now let \(u\in D''\cap V(S^{ir})\) for some edge \(v_iv_r\in E(G)\). If \(u=c^{ir}\), then \(\deg_{G'}(u)=k+2\) and both \(b^{ir}\) and \(v_i\) belong to \(N_{G'}(u)\cap D''\), so \(|N_{G'}(u)\setminus D''|\le k\). For \(u\in \{b^{ir}, x^{ir}_1, \ldots, x^{ir}_k\}\) we have \(|N_{G'}(u)\setminus D''|=1< k\). For all remaining vertices of \(D''\), the number of neighbors outside the set remains the same, so the \(k\)-limited constraint continues to hold, and \(D''\) is again a \(k\)-limited dominating set of \(G'\).
Finally, the modification ensures that the original vertex \(v_i\) is now selected in \(D''\), since \(D''\cap V(G)=D_0\cup\{v_i\}\). Consequently, \(v_i\) is no longer undominated in \(G\).
If the set of original vertices of contained in \(D''\) does not yet dominate \(G\), we repeat the same process. Since at each step the set of undominated vertices in \(G\) is strictly reduced and \(V(G)\) is finite, the procedure terminates after finitely many steps. Thus we obtain a \(k\)-limited dominating set \(\widehat{D}\) of \(G'\) with \(|\widehat{D}|\le |D'|\) such that the set of original vertices contained in \(\widehat{D}\) forms a dominating set of \(G\).
It remains to bound its size. Since \(\widehat{D}\) is again a \(k\)-limited dominating set of \(G'\), the argument above applies to \(\widehat{D}\) as well: every gadget contributes at least \(k+2\) vertices to \(\widehat{D}\). Hence \[|\widehat{D}\cap V(G)| =|\widehat{D}|-\sum_{v_iv_j\in E(G)} |\widehat{D}\cap V(S^{ij})| \le |\widehat{D}|-(k+2)m \le |D'|-(k+2)m \le \ell.\] Therefore \(\widehat{D}\cap V(G)\) is a dominating set of \(G\) of size at most \(\ell\). This completes the proof. ◻
Proposition 4 establishes the correctness of the reduction. Since the reduction is polynomial and \(k\)-Limited Dominating set belongs to \(\mathsf{NP}\), we obtain the following.
Theorem 5. For every fixed integer \(k\ge 2\), the \(k\)-Limited Dominating set problem is \(\mathsf{NP}\)-complete.
In the case \(k=2\), our reduction produces bipartite instances. Indeed, subdividing every edge of \(G\) once yields a bipartite graph, and the gadget \(S\) for \(k=2\) is bipartite as well. Hence the graph \(G'\) constructed by the reduction is bipartite. Therefore, the same reduction shows that the hardness result extends to bipartite graphs. Consequently, we obtain the following.
Corollary 1. \(2\)-Limited Dominating set problem is \(\mathsf{NP}\)-complete even when restricted to bipartite graphs.
4 Cartesian product↩︎
We next investigate how \(k\)-limited domination behaves under the Cartesian product of graphs. The following theorem provides general lower and upper bounds for \(\gamma_k^{\mathrm L}(G \square H)\). We get the lower bound by a direct counting argument, while the upper bound is obtained by taking an optimal \(k\)-limited dominating set in one factor and repeating it in every layer corresponding to the other factor.
Theorem 6. Let \(G\) and \(H\) graphs, and let \(k\geq 1\) be an integer. Then \[\left\lceil \frac{n(G)\, n(H)}{k+1} \right\rceil \le \gamma_k^{\mathrm L}(G \square H) \le \min\big\{\gamma_k^{\mathrm L}(G)\,n(H),\, \gamma_k^{\mathrm L}(H)\,n(G)\big\}.\]
Proof. Let \(D\) be a \(k\)-limited dominating set of \(G \square H\). For each vertex \(x\in D\), the set \(\{x\}\cup \bigl(N_{G\square H}(x)\setminus D\bigr)\) has size at most \(k+1\), since \(|N_{G\square H}(x)\setminus D|\le k\) by the \(k\)-limited constraint. Moreover, because \(D\) dominates \(G\square H\), every vertex of \(G\square H\) belongs either to \(D\) or to \(N_{G\square H}(x)\setminus D\) for some \(x\in D\). Hence \[V(G\square H)\subseteq \bigcup_{x\in D}\Bigl(\{x\}\cup \bigl(N_{G\square H}(x)\setminus D\bigr)\Bigr),\] and therefore \[n(G)\, n(H)=|V(G\square H)| \leq \sum_{x\in D}(k+1) = (k+1)|D|,\] which yields the lower bound.
For the upper bound, let \(D_G \subseteq V(G)\) be a \(\gamma^{\mathrm L}_k(G)\)-set. Let \(D = D_G \times V(H) \subseteq V(G \square H)\). We claim that \(D\) is a \(k\)-limited dominating set of \(G \square H\).
Let \((u,v)\in V(G \square H)\setminus D\) be arbitrary. Then \(u \notin D_G\). As \(D_G\) is, in particular, a dominating set of \(G\), there exists a vertex \(x \in D_G\) with \(ux \in E(G)\). Then \((u,v)\) and \((x,v)\) are adjacent in \(G \square H\), and \((x,v) \in D\). Hence \(D\) dominates \(G \square H\).
To verify the \(k\)-limited constraint now let \((u,v)\) be an arbitrary vertex in \(D\). Then \(u \in D_G\) and \(v \in V(H)\). There are two types of neighbors of \((u,v)\) in \(G \square H\): \((u',v)\) with \(u'u \in E(G)\), and \((u,v')\) with \(vv' \in E(H)\). Since \(D = D_G \times V(H)\), for every \(v' \in V(H)\) we have \((u,v') \in D\). Since \(D=D_G\times V(H)\), every neighbor of second type also belongs to \(D\). Therefore \(N_{G\square H}((u,v))\setminus D = \{(u',v): u'u\in E(G),\;u'\notin D_G\},\) and consequently \(|N_{G\square H}((u,v))\setminus D| = |N_G(u)\setminus D_G|.\) Because \(D_G\) is a \(k\)-limited dominating set of \(G\), we have \(|N_G(u)\setminus D_G|\le k\) for every \(u\in D_G\). Hence \(|N_{G\square H}((u,v))\setminus D|\le k\) for every \((u,v)\in D\). Thus \(D\) is a \(k\)-limited dominating set of \(G\square H\), and so \[\gamma_k^{\mathrm L}(G\square H) \le |D| =|D_G|\,n(H) =\gamma_k^{\mathrm L}(G)\, n(H).\] By symmetry, interchanging the roles of \(G\) and \(H\) yields \(\gamma_k^{\mathrm L}(G\square H)\le \gamma_k^{\mathrm L}(H)\, n(G).\) Taking the minimum of the two upper bounds completes the proof. ◻
In the subsequent subsections, we show that both bounds in Theorem 6 are sharp, and we derive closed formulas for \(\gamma_k^{\mathrm L}\) for several well-known families of graphs.
4.1 Rook graphs↩︎
To show that the upper bound in Theorem 6 is tight, we now turn to Cartesian products of complete graphs, also known as rook graphs.
It is easy to see that for every nontrivial connected graph \(H\) there exists a \(k\)-limited dominating set in \(K_{k+2}\square H\) of size \(2n(H)\), namely the set \(D=\{x_1,x_2\}\times V(H)\), where \(x_1\) and \(x_2\) are arbitrary vertices of \(K_{k+2}\). Consequently, \(\gamma_k^{\mathrm L}(K_{k+2}\square H)\le 2n(H)\). Whether this bound is attained depends on the structure of \(H\). For instance, if \(H=K_{k+1}\), then, by Theorem 6 and Proposition 3, we have \(\gamma_k^{\mathrm L}(K_{k+2}\square H)\le k+2<2 n(H)\). On the other hand, equality does hold in the special case when \(H=K_{k+2}\), as shown in the following proposition.
Proposition 7. Let \(k\) be a positive integer. Then \(\gamma_k^{\mathrm L}(K_{k+2} \square K_{k+2})=2(k+2)\).
Proof. Let \(m=k+2\). Then \(\Delta(K_m)=m-1=k+1\), and hence \(1\le k<\Delta(K_m)\). Thus \(\gamma_k^{\mathrm L}(K_m)=m-k=2\) by Proposition 3. Applying Theorem 6 with \(G=H=K_m\) yields \[\gamma_k^{\mathrm L}(K_m \square K_m)\leq \gamma_k^{\mathrm L}(K_m) \, |V(K_m)|=2m=2(k+2).\] To complete the proof it remains to show that \(\gamma_k^{\mathrm L}(K_m \square K_m)\geq 2m\).
Let \(D\) be a \(\gamma_k^{\mathrm L}(K_m \square K_m)\)-set, and let \(V(K_m \square K_m) = \{(i,j) : 1 \le i,j \le m\}\). For each \(j\in [m]\) we define the \(j\)th row \(R_j = \{(i,j) : 1\le i\le m\}\), and for each \(i\in [m]\) the \(i\)th column \(C_i = \{(i,j) : 1\le j\le m\}\). For each \(j\in [m]\) let \(r_j = |D\cap R_j|\), and for each \(i\in [m]\) let \(c_i = |D\cap C_i|\). Then \[\sum_{j=1}^m r_j = |D| = \sum_{i=1}^m c_i.\]
We first note that no row and no column contains exactly one vertex of \(D\), as the opposite case contradicts the \(k\)-limited constraint. Thus \(r_j \ne 1\) for all \(j\in [m]\) and \(c_i \ne 1\) for all \(i\in[m]\).
Now suppose, to the contrary, that \(|D|\le 2m-1\). Then \[\frac{1}{m} \sum_{j=1}^m r_j = \frac{|D|}{m} \le \frac{2m-1}{m} < 2,\] hence there exists a row \(R_{j_0}\) with \(r_{j_0} \le 1\). Since \(r_{j_0} \ne 1\), we must have \(r_{j_0} = 0\), that is, the row \(R_{j_0}\) contains no vertex in \(D\). Applying the same argument to the sum \(\sum_{i=1}^m c_i\) shows that there exists a column \(C_{i_0}\) with no vertex in \(D\). But then the vertex \((i_0,j_0)\) has no neighbor in \(D\), contradicting the fact that \(D\) is a dominating set of \(K_m \square K_m\).
Therefore \(|D|\ge 2m\). Combining this inequality with the upper bound derived above concludes the proof. ◻
Corollary 2. For every positive integer \(k\), the upper bound in Theorem 6 is attained.
4.2 Cartesian products of \(k\)-coronas↩︎
By considering Cartesian products of \(k\)-coronas we now show that the lower bound in Theorem 6 is sharp as well.
Recall that the corona product \(G\circ H\) is obtained from one copy of \(G\) and \(n(G)\) disjoint copies of \(H\) by joining each vertex of \(G\) to all vertices in the corresponding copy of \(H\). In particular, \(G\circ \overline{K_k}\) is obtained from \(G\) by attaching \(k\) leaves to each vertex of \(G\), and we call this graph the \(k\)-corona of \(G\).
Lemma 1. Let \(k\ge 1\) and let \(F\) be a graph. Let \(G=F\circ \overline{K_k}\). Then \[\gamma_k^{\mathrm L}(G)=\frac{n(G)}{k+1}.\]
Proof. Let \(U=V(F)\), viewed as a subset of \(V(G)\). Since every vertex of \(U\) has exactly \(k\) pendant neighbors outside \(U\), while all its remaining neighbors also belong to \(U\), the set \(U\) is a \(k\)-limited dominating set of \(G\). Hence \(\gamma_k^{\mathrm L}(G)\le|U|=\frac{n(G)}{k+1}.\)
For the reverse inequality, let \(D\) be a \(\gamma_k^{\mathrm L}(G)\)-set. For each \(u\in U\), let \(L_u\) denote the set of the \(k\) leaves adjacent to \(u\), and set \(B_u=\{u\}\cup L_u.\) Then the sets \(B_u\), for \(u\in U\), form a partition of \(V(G)\). Moreover, for each \(u\in U\), at least one vertex of \(B_u\) must belong to \(D\), since otherwise none of the leaves in \(L_u\) would be dominated. Therefore \(|D|\ge |U|=\frac{n(G)}{k+1}.\) Combining the two inequalities yields the result. ◻
Now Theorem 6 immediately gives the following.
Proposition 8. Let \(k\ge 1\) and let \(F\) and \(F'\) be graphs. Let \(G=F\circ \overline{K_k}\) and \(H=F'\circ \overline{K_k}\). Then \[\gamma_k^{\mathrm L}(G\square H)=\frac{n(G)\,n(H)}{k+1}.\]
Proof. By Lemma 1, \(\gamma_k^{\mathrm L}(G)=\frac{n(G)}{k+1}\) and \(\gamma_k^{\mathrm L}(H)=\frac{n(H)}{k+1}\). Therefore the upper bound in Theorem 6 gives \(\gamma_k^{\mathrm L}(G\square H)\le \frac{n(G)\,n(H)}{k+1}\). On the other hand, the lower bound in the same theorem and the identity \(n(G\square H)=n(G)\,n(H)\) yield the reverse inequality. ◻
Corollary 3. The lower bound in Theorem 6 is attained for every positive integer \(k\).
4.3 Grid graphs↩︎
Having established the sharpness of both bounds in Theorem 6, we now focus on more specific results for the case \(k=1\). We begin with grid graphs, that is, Cartesian products of two paths, for which Theorem 6 already yields an exact formula whenever at least one of the two paths has even order.
Lemma 2. Let \(m,n\ge 1\) be integers, where at least one of them is even. Then \[\gamma_1^{\mathrm L}(P_m \square P_n) = \frac{mn}{2}.\]
Proof. Without loss of generality, assume that \(m\) is even. Then \(mn\) is even, and the lower bound in Theorem 6 gives \[\gamma_1^{\mathrm L}(P_m\square P_n) \ge \left\lceil \frac{n(P_m\square P_n)}{2} \right\rceil = \left\lceil \frac{mn}{2} \right\rceil = \frac{mn}{2}.\] On the other hand, Theorem 6 and Proposition 3 yield \[\gamma_1^{\mathrm L}(P_m\square P_n) \le \min\left\{\frac{mn}{2},\left\lceil\frac{n}{2}\right\rceil m\right\} = \frac{mn}{2}.\] Hence equality holds. ◻
On the other hand, if \(2\le m\le n\) are both odd, determining the \(1\)-limited domination number of \(P_m\square P_n\) appears to be more challenging. In this case, Theorem 6 gives \[\frac{mn+1}{2} \le \gamma_1^{\mathrm L}(P_m\square P_n) \le \min\left\{\frac{(m+1)n}{2},\frac{(n+1)m}{2}\right\} = \frac{mn+m}{2} = m\Big\lceil \frac{n}{2} \Big\rceil,\] where the last equality uses the assumption \(m\le n\). We will show that when \(m=3\), equality holds in the upper bound. To this end, we first fix the notation.
For an integer \(n\geq 2\) let \(G_n = P_n\square P_3\). More precisely, let \(V(G_n) = \{a_i,c_i,b_i : 1\le i\le n\}\), and \(E(G_n) = \{a_ic_i,\,c_ib_i : 1\le i\le n\} \,\cup\, \{x_ix_{i+1} : x\in\{a,c,b\},\,1\le i\le n-1\}.\) For \(1\le i\le n\) we call \(T_i = \{a_i,c_i,b_i\}\) the \(i\)-th column of \(G_n\); it induces a copy of \(P_3\). Given a \(1\)-limited dominating set \(D\subseteq V(G_n)\) we define, for each column \(T_i\), \(t_i = |D\cap T_i|\in\{0,1,2,3\}\). We call \((t_1,\dots,t_n)\) the column weight sequence of \(D\), and denote it briefly by \((t_i)\). A column \(T_i\) is called empty if \(t_i=0\) and full if \(t_i=3\).
First we analyze possible column weight sequences of \(1\)-limited dominating sets. We view consecutive subsequences of \((t_i)\) as patterns, encoded by the corresponding strings over the alphabet \(\{0,1,2,3\}\). For example, if for some \(j\) we have \((t_j,t_{j+1},t_{j+2})=(0,3,3)\), we say that \((t_i)\) contains the pattern \(033\) at position \(j\).
In addition to forbidden local patterns, one of the key observations, formalized in the following lemma, is that every column of weight \(0\) or \(1\) has a private neighbor of weight \(3\), that is, no two distinct columns of weight \(0\) or \(1\) share the same neighboring column of weight \(3\).
Lemma 3. Let \(n\geq 3\) and let \(D\) be a \(1\)-limited dominating set of \(G_n\). Then the following holds.
None of the following patterns occurs in \((t_i)\): \[01,\;10,\;12,\;21,\;20,\;02,\;000,\;111,\;230,\;032,\;030,\;130,\;031,\;131.\]
Let \(S=\{i\in [n]:\;t_i\in \{0,1\}\}\). Then for every \(i\in S\) there exists \(j\in [n]\) with \(|i-j|=1\) and \(t_j=3\). Moreover, there is an injective map \(p:S\to [n]\) such that \(|p(i)-i|=1\) and \(t_{p(i)}=3\) for all \(i\in S\).
Proof. A straightforward case analysis on two or three consecutive columns shows that the configurations corresponding to the patterns listed in (a) are incompatible with \(1\)-limited domination. To prove (b), let \(i\in S\), so \(t_i\in\{0,1\}\).
Assume first that \(t_i=0\). By (a), none of the patterns \(01,02,10,20\) can occur, and hence each neighbor of \(T_i\) has weight either \(0\) or \(3\). If \(1<i<n\) and neither neighboring column had weight \(3\), then \((t_{i-1},t_i,t_{i+1})=(0,0,0)\), contradicting the forbidden pattern \(000\). Thus in this case there exists a neighboring column of weight \(3\). The same conclusion holds when \(i\in\{1,n\}\). Indeed, if \(i=1\), then by (a) neither \(01\) nor \(02\) can occur, so the only remaining possibilities are \(t_2=0\) or \(t_2=3\). The case \(t_2=0\) is impossible, since then not all vertices of \(T_1\) are dominated. Hence \(t_2=3\). The case \(i=n\) is symmetric.
Assume now that \(t_i=1\). By (a), none of the patterns \(10,01,12,21\) can occur, and hence each neighbor of \(T_i\) has weight either \(1\) or \(3\). If \(1<i<n\) and neither neighboring column had weight \(3\), then \((t_{i-1},t_i,t_{i+1})=(1,1,1)\), contradicting the forbidden pattern \(111\). Thus in this case there exists a neighboring column of weight \(3\). It remains to consider the boundary cases. By symmetry, it suffices to treat \(i=1\). Suppose, to the contrary, that \(t_1=t_2=1\). Let \(x\) be the unique vertex of \(D\cap T_1\), and let \(y\) be the unique vertex of \(D\cap T_2\). First note that \(x\neq c_1\), since otherwise \(x\) would have both \(a_1\) and \(b_1\) as neighbors outside \(D\), contradicting the \(1\)-limited condition. Hence, by symmetry, we may assume that \(x=a_1\). Since \(b_1\) must be dominated and \(x\) does not dominate it, we must have \(y=b_2\). But then the vertex \(y\) has both \(b_1\) and \(c_2\) as neighbors outside \(D\), again contradicting the \(1\)-limited condition. Therefore \(t_2\ne 1\), and since (a) excludes \(t_2=2\), we must have \(t_2=3\). The case \(i=n\) is symmetric. Thus, whenever \(t_i\in\{0,1\}\), there exists a neighboring column of weight \(3\).
Finally, we show that two distinct columns of weight \(0\) or \(1\) cannot share the same neighboring column of weight \(3\). Indeed, if there exists \(\ell\) such that \(t_\ell\in\{0,1\}\), \(t_{\ell+1}=3\), and \(t_{\ell+2}\in\{0,1\}\), then \((t_\ell,t_{\ell+1},t_{\ell+2})\) is one of the forbidden patterns \(030,031,130,131\), contradicting (a).
Therefore, for each \(i\in S\) we may choose a neighboring index \(p(i)\in[n]\) with \(|p(i)-i|=1\) and \(t_{p(i)}=3\), and the previous paragraph shows that this choice yields an injective map \(p:S\to[n]\). ◻
Proposition 9. Let \(n\geq 3\) be an odd integer. Then \(\gamma_1^{\mathrm L}(G_n)\geq \frac{3}{2}n+\frac{3}{2}\).
Proof. Let \(D\) be a \(\gamma_1^{\mathrm L}(G_n)\)-set, and let \((t_1,\dots,t_n)\) be the corresponding column weight sequence. Define \[\begin{align} S&=\{i\in[n]: t_i\in\{0,1\}\},\qquad &O&=\{i\in[n]: t_i=1\},\\ T&=\{i\in[n]: t_i=2\},\qquad &H&=\{i\in[n]: t_i=3\}. \end{align}\] By Lemma 3 (b), there exists an injective map \(p:S\to[n]\) such that \(|p(i)-i|=1\) and \(t_{p(i)}=3\) for all \(i\in S\). Let \(R=H\setminus p(S)\). Since \(p\) is injective, we have \(|H|=|S|+|R|\). Now \[|D|=\sum_{i=1}^n t_i = |O|+2|T|+3|H| =|O|+2|T|+3|S|+3|R|,\] while \[n=|S|+|T|+|H|=2|S|+|T|+|R|.\] Therefore \[|D|-\frac{3}{2}n = |O|+\frac{1}{2}|T|+\frac{3}{2}|R|.\] Hence it suffices to prove that \[|O|+\frac{1}{2}|T|+\frac{3}{2}|R|\ge \frac{3}{2}.\] If \(|R|\ge 1\), then we are done. Thus assume \(R=\emptyset\). Then \(|H|=|S|\), and so \(n=|S|+|T|+|H|=2|S|+|T|\). Since \(n\) is odd, it follows that \(|T|\) is odd. If \(|T|\ge 3\), then \(\frac{1}{2}|T|\ge \frac{3}{2}\), and again we are done. Thus \(|T|=1\). We claim that then \(|O|\ge 1\).
Suppose for a contradiction that \(|O|=0\). Then every index in \(S\) corresponds to an empty column. Let \(r\) be the unique index with \(t_r=2\). By Lemma 3(a), the patterns \(02\) and \(20\) are forbidden. Hence every column adjacent to \(T_r\) has weight \(3\). Since \(R=\emptyset\), every full column belongs to \(p(S)\), and hence is adjacent to some empty column. If \(r=1\), then \(t_2=3\), and the empty column adjacent to \(T_2\) must be \(T_3\), yielding the forbidden pattern \(230\). If \(r=n\), then \(t_{n-1}=3\), and the empty column adjacent to \(T_{n-1}\) must be \(T_{n-2}\), yielding the forbidden pattern \(032\). If \(1<r<n\), then both neighboring columns of \(T_r\) have weight \(3\). Since \(R=\emptyset\) and \(|O|=0\), each of these full columns must be adjacent to an empty column on its other side. Hence \((t_{r-2},t_{r-1},t_r,t_{r+1},t_{r+2})=(0,3,2,3,0),\) which contains the forbidden patterns \(032\) and \(230\).
This contradiction proves that \(|O|\ge 1\). Consequently, in the remaining case \(|T|=1\) we have \(|O|+\frac{1}{2}|T|\ge 1+\frac{1}{2}=\frac{3}{2},\) which completes the proof. ◻
The above observations can now be summarized as follows.
Theorem 10. For every integer \(n\ge 2\), we have \(\gamma_1^{\mathrm L}(P_n\square P_3) = 3\,\Big\lceil\frac{n}{2}\Big\rceil\).
Proof. For even \(n\) the proof follows from Lemma 2. For odd \(n\), Proposition 9 gives us \(\gamma_1^{\mathrm L}(P_n\square P_3) \geq 3\,\Big\lceil\frac{n}{2}\Big\rceil\), while the opposite inequality clearly follows from Theorem 6. ◻
4.4 Hypercubes↩︎
Hypercubes form a particularly well-structured class in which \(k\)-limited domination can be studied explicitly: they are highly symmetric, regular, and arise recursively as iterated prisms. In this subsection we first recall a useful reduction for regular graphs, then discuss prisms, and finally apply these observations to \(Q_d\).
In [8] the following was proved for regular graphs.
Proposition 11. [8] Let \(G\) be a connected \(d\)-regular graph of order \(n\geq 3\) and let \(k\) be an integer such that \(1\leq k<d\). Then \(\gamma_k^{\mathrm L}(G)=\gamma_{1,d-k}(G)\).
Before turning specifically to hypercubes, let us briefly discuss what can be said about \(k\)-limited domination on general prisms. Recall that the prism over a graph \(G\) is the Cartesian product \(G\square K_2\). Several domination parameters behave particularly well on prisms. In particular, it was shown in [15], and subsequently reproved by different arguments in [16] and [17], that if \(G\) is a bipartite graph, then \(\gamma_t(G\square K_2)=2\gamma(G)\).
Now let \(G\) be a connected \(d\)-regular bipartite graph. Then \(G\square K_2\) is \((d+1)\)-regular, and Proposition 11 applied to \(G\square K_2\) with \(k=d\) gives \(\gamma_d^{\mathrm L}(G\square K_2)=\gamma_{1,1}(G\square K_2)=\gamma_t(G\square K_2)\). Combining this with the above identity yields the following.
Corollary 4. Let \(G\) be a connected \(d\)-regular bipartite graph with \(d\ge 2\). Then \[\gamma_d^{\mathrm L}(G\square K_2) = 2\,\gamma(G).\]
Hypercubes fit naturally into this picture as for every \(d\ge 1\) we have the recursive representation \(Q_{d+1}=Q_d\square K_2\), so that \(Q_{d+1}\) is precisely the prism over \(Q_d\). Since \(Q_d\) is \(d\)-regular and bipartite, Corollary 4 immediately yields the following relationship.
Corollary 5. Let \(d\ge 1\) be an integer. Then \(\gamma_d^{\mathrm L}(Q_{d+1}) =\gamma_t(Q_{d+1})= 2\,\gamma(Q_d)\).
For hypercubes, exact formulas for the classical domination number are known only for small values (see Table 3) and for two distinguished infinite families. Namely, if \(d=2^r-1\), then \(\gamma(Q_d)=2^{\,2^r-r-1}\), while for \(d=2^r\) one has \(\gamma(Q_d)=2^{\,2^r-r}\). The first formula follows from the existence of perfect codes in \(Q_{2^r-1}\), see [5], while the second is due to van Wee [6]. Consequently, Corollary 5 immediately yields exact values for \(\gamma^{\mathrm L}_{d-1}(Q_d)\) in the corresponding families.
Corollary 6. Let \(r\ge 1\) be an integer. If \(d=2^r\), then \(\gamma^{\mathrm L}_{d-1}(Q_d)=2^{\,2^r-r}\), and if \(d=2^r+1\), then \(\gamma^{\mathrm L}_{d-1}(Q_d)=2^{\,2^r-r+1}\).
While the previous corollaries concern the extremal case \(k=d\), the opposite end \(k=1\) leads to a simpler behavior. In fact, optimal \(1\)-limited dominating sets in \(Q_d\) occupy exactly one half of the vertices. We include a short proof, which also illustrates how the general Cartesian product bounds become tight on hypercubes.
Proposition 12. For every integer \(d\ge 1\), \(\gamma_1^{\mathrm L}(Q_d) = 2^{d-1}\).
Proof. Since \(Q_d\) has \(2^d\) vertices, the lower bound in Theorem 2 gives \(\gamma_1^{\mathrm L}(Q_d)\ge \left\lceil \frac{2^d}{2}\right\rceil = 2^{d-1}\).
To prove the opposite inequality, recall that for an integer \(d\ge 1\), \(Q_d\) can be seen as the graph with \(V(Q_d)=\{(x_1,\dots,x_d): x_i\in\{0,1\}\text{ for all }i\in[d]\}\), where two vertices are adjacent if and only if they differ in exactly one coordinate. Let \(D=\{(x_1,\dots,x_d)\in\{0,1\}^d:\;x_1=0\}\). Clearly \(|D|=2^{d-1}\). We claim that \(D\) is a \(1\)-limited dominating set of \(Q_d\). Take an arbitrary vertex \(y=(y_1,\dots,y_d)\notin D\), so \(y_1=1\). Then the vertex \(x=(0,y_2,\dots,y_d)\in D\) differs from \(y\) in exactly one coordinate, hence \(x\) and \(y\) are adjacent \(Q_d\). Therefore \(D\) dominates every vertex outside \(D\). To verify the \(1\)-limited constraint, let \(x\in D\). Among the \(d\) neighbors of \(x\), exactly one has first coordinate \(1\), while the remaining \(d-1\) neighbors have the first coordinate equal to \(0\) and thus also lie in \(D\). Consequently, \(x\) dominates exactly one vertex of \(V(Q_d)\setminus D\), and the \(1\)-limited constraint holds. Thus \(\gamma_1^{\mathrm L}(Q_d)\le |D|=2^{d-1}\), and together with the lower bound we conclude \(\gamma_1^{\mathrm L}(Q_d)=2^{d-1}\). ◻
5 Conclusion↩︎
The notion of \(k\)-limited domination was introduced in [8] as a restricted variant of classical domination, motivated by situations in which dominating vertices cannot serve arbitrarily many vertices outside the dominating set. The present paper shows that the parameter is not only well motivated, but also structurally rich and mathematically nontrivial.
This is reflected already in the computational complexity of the problem. While we proved that \(k\)-Limited Dominating set is \(\mathsf{NP}\)-complete for every fixed integer \(k\ge 2\), the extremal case \(k=1\) remains unresolved. Our reduction relies in an essential way on the assumption \(k\ge 2\), and the corresponding forcing mechanism breaks down for \(k=1\). This suggests that the case of \(1\)-limited domination requires a different approach, and leads naturally to the following question.
Problem 13. Is \(1\)-Limited Dominating Set \(\mathsf{NP}\)-complete?
Another direction pursued in this paper concerns the behavior of \(k\)-limited domination under the Cartesian product. We established general lower and upper bounds for \(\gamma_k^{\mathrm L}(G\square H)\), proved that both are sharp, and derived exact values for several natural graph families. In particular, for \(k=1\) all exact values obtained in this paper attain the general upper bound from Theorem 6. This is not the typical behavior for arbitrary \(k\): for example, \(\gamma^{\mathrm L}_2(K_2\square K_{1,3})=3\), whereas Theorem 6 yields only the upper bound \(4\). Nevertheless, our results suggest that the extremal case \(k=1\) may be special, which leads to the following question.
Problem 14. Is it true that for all connected graphs \(G\) and \(H\), \[\gamma^{\mathrm L}_1(G\square H)= \min\big\{\gamma^{\mathrm L}_1(G)\,n(H),\, \gamma^{\mathrm L}_1(H)\,n(G)\big\}\, ?\]
A particularly natural case to examine is the Cartesian product of two paths. In this paper we proved that \(\gamma_1^{\mathrm L}(P_m\square P_n)=\frac{mn}{2}\) whenever at least one of \(m\) and \(n\) is even, and that \(\gamma_1^{\mathrm L}(P_n\square P_3)=3\lceil \frac{n}{2}\rceil\). This leaves open the case when \(m\) and \(n\) are both odd, and leads to the following question.
Problem 15. Is it true that for all integers \(1\le m\le n\), \(\gamma^{\mathrm L}_1(P_m\square P_n)= m\lceil \frac{n}{2}\rceil\)?
We conclude by discussing \(k\)-limited domination in hypercubes. For the classical domination number \(\gamma(Q_d)\), a useful overview of the current state of knowledge is provided by the recent paper of Wu and Chen [7], whose appendix collects the best known lower and upper bounds for dimensions up to \(33\). In addition, for dimensions divisible by \(6\), their main theorem improves some of the previously best known lower bounds. The gray cells in Table 3 reflect the corresponding part of this picture up to dimension \(17\), while incorporating the mentioned improvement in the case \(d=12\). The remaining entries are then arranged around these values in the setting of \(k\)-limited domination. Since for \(k\ge d\) we have \(\gamma_k^{\mathrm L}(Q_d)=\gamma(Q_d)\), an asterisk indicates that the corresponding value coincides with the one in the gray cell above it. The entries immediately above the gray cells represent the values of \(\gamma_{d-1}^{\mathrm L}(Q_d)\), which, by Corollary 5, are equal to the total domination number \(\gamma_t(Q_d)\), and therefore to twice the domination number of the \((d-1)\)-dimensional hypercube. The values in the first row follow from Proposition 12.
For \(d\)-regular graphs, and in particular for hypercubes \(Q_d\), the identity \(\gamma_k^{\mathrm L}(Q_d)=\gamma_{1,d-k}(Q_d)\), arising from Proposition 11, shows that the study of \(k\)-limited domination is naturally equivalent to the study of \((1,t)\)-domination. As already noted, the case \(t=1\) corresponds to total domination, while the cases \(t\ge 2\) seem to remain largely open. In particular, the parameter \(\gamma^{\mathrm L}_{d-2}(Q_d)\), equivalent to \((1,2)\)-domination, appears to be a natural next direction for further research, especially in light of the recent interest in this parameter [12], [18], [19].
| \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) | \(15\) | \(16\) | \(17\) | |||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(\gamma^{\mathrm L}_1(Q_d)\) | \(2\) | \(4\) | \(8\) | \(16\) | \(32\) | \(64\) | \(128\) | \(256\) | \(512\) | \(1024\) | \(2048\) | \(4096\) | \(8192\) | \(16384\) | \(32768\) | \(65536\) | |||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_2(Q_d)\) | \(*\) | \(4\) | |||||||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_3(Q_d)\) | \(*\) | \(*\) | \(4\) | ||||||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_4(Q_d)\) | \(*\) | \(*\) | \(*\) | \(8\) | |||||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_5(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(14\) | ||||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_6(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(24\) | |||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_7(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(32\) | ||||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_8(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(64\) | |||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_9(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(124\) | ||||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{10}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(214\)–\(240\) | |||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{11}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | 360–384 | ||||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{12}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | 696–760 | |||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{13}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | 1196–1408 | ||||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{14}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | 2344–2816 | |||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{15}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(4096\) | ||||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{16}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(8192\) | |||||||||||||||||||||||||||||||||||
| \(\gamma^{\mathrm L}_{17}(Q_d)\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) | \(*\) |
3.5pt
From this perspective, filling the blank cells of Table 3 is already an interesting problem in its own right. More specifically, it would be desirable to determine further exact values of \(\gamma_k^{\mathrm L}(Q_d)\) and to gain a more systematic understanding of how these parameters behave as \(k\) tends to \(d\).
This work has been supported by the European Commission’s Horizon Europe Research and Innovation programme through the Marie Skłodowska-Curie Actions Staff Exchanges (MSCA-SE) under Grant Agreement no. 101182819 (COVER: (C)ombinatorial (O)ptimization for (V)ersatile Applications to (E)merging u(R)ban Problems). The researcher was partially supported by Slovenian research agency ARIS, program no. P1–0297 and project no. J1–70016.