On k-limited domination in graphs

Abstract A set of vertices is called a k -limited dominating set if every vertex of the graph is either contained in the set or adjacent to a vertex of the set, and each vertex of the set has at most k neighbors outside the set. The minimum cardinality among all k -limited dominating sets of G is the k-limited domination number , denoted by $$\gamma _k^{\mathrm L}(G)$$ γ k L ( G ) . Since $$\Delta (G)$$ Δ ( G ) -limited domination coincides with the classical domination, we restrict our attention to the nontrivial range $$1 \le k < \Delta (G)$$ 1 ≤ k < Δ ( 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)$$ γ k L ( 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)=\gamma _{1,d-k}(G)$$ γ k L ( G ) = γ 1 , d - k ( G ) . In the special case $$k=1$$ k = 1 , we show that 1-limited domination is tightly linked to graph packings, yielding the tight bound $$\gamma ^{\mathrm L}_1(G) \le n - \rho (G)$$ γ 1 L ( G ) ≤ n - ρ ( G ) . The study reveals several natural open questions and indicates that limited domination provides a rich ground for further research.