On k-limited domination in graphs

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 γ ₖL(G) γ k L ( G ) . Since Δ (G) Δ ( G ) -limited domination coincides with the classical domination, we restrict our attention to the nontrivial range 1 ≤ k < Δ (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 γ ₖ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 γ ₖL(G)=γ 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 γ L₁(G) ≤ n - ρ (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.