On $k$-limited domination in graphs

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 }_1^{\mathrm{L}}(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.