View PDF HTML (experimental)

Abstract:In this work, we introduce and study the notion of $k$-limited domination in graphs, motivated by applications where dominating vertices have bounded capacity and cannot be overloaded by too many external neighbors. Formally, given an integer $k \le \Delta(G)$, a set of vertices $D \subseteq V(G)$ is called a $k$-limited dominating set if it is a dominating set and, in addition, each vertex of $D$ has at most $k$ neighbors outside $D$. The minimum cardinality of such a set is the $k$-limited domination number, denoted by $\gamma_k^{\mathrm{L}}(G)$. Since $\Delta(G)$-limited domination coincides with the classical domination, we restrict our attention to the nontrivial range $1 \le k < \Delta(G)$, where the degree limitation becomes meaningful and leads to new combinatorial phenomena.
In this paper, we initiate the study of this concept by deriving sharp general bounds for $\gamma_k^{\mathrm{L}}(G)(G)$ and identifying conditions under which these bounds can be further improved. We establish a connection between $k$-limited domination and $(1,t)$-domination. In particular, for $d$-regular graphs we prove that $\gamma_k^{\mathrm{L}}(G)(G)=\gamma_{1,d-k}(G)$. In the special case $k=1$, we show that $1$-limited domination is tightly linked to graph packings, yielding the bound $\gamma^{\mathrm L}_1(G) \le n - \rho(G)$ and its characterization.
The study reveals several natural open questions and indicates that limited domination provides a rich ground for further research.

Submission history

From: Aleksandra Tepeh [view email]
[v1] Sun, 21 Jun 2026 10:18:32 UTC (20 KB)