Component domination in regular graphs

A dominating set in a graph 𝐺 is a set 𝑆 of vertices of 𝐺 such that every vertex in 𝑉 ⁡ ( 𝐺 ) ∖ 𝑆 is adjacent to a vertex in 𝑆 . For 𝑘 ≥ 1 an integer, a 𝑘 -component dominating set first defined by Alvarado, Dantas, and Rautenbach [Discrete Math. 339 (2016), 2715–2720] is a dominating set 𝑆 with the additional property that every component in the subgraph, 𝐺 ⁡ [ 𝑆 ] , of 𝐺 induced by 𝑆 has order at least 𝑘 . The 𝑘 -component domination number 𝛾 𝑘 ⁡ ( 𝐺 ) is the minimum cardinality among all 𝑘 -component dominating sets of 𝐺 . We observe that the 𝑘 -component domination number provides a natural generalization of both the domination number 𝛾 ⁡ ( 𝐺 ) and the total domination number 𝛾 𝑡 ⁡ ( 𝐺 ) since 𝛾 1 ⁡ ( 𝐺 ) = 𝛾 ⁡ ( 𝐺 ) and 𝛾 2 ⁡ ( 𝐺 ) = 𝛾 𝑡 ⁡ ( 𝐺 ) . The upper 𝑘 -component domination number 𝛤 𝑘 ⁡ ( 𝐺 ) of 𝐺 is the maximum cardinality among all minimal 𝑘 -component dominating sets of 𝐺 . For 𝑟 ≥ 2 , let 𝐺 be a connected 𝑟 -regular graph of order 𝑛 . We show that for all 𝑘 ≥ 1 , 𝛾 𝑘 ⁡ ( 𝐺 ) ≥ ( 𝑘 𝑘 ⁢ ( 𝑟 − 1 ) + 2 ) ⁢ 𝑛 and 𝛤 𝑘 ⁡ ( 𝐺 ) ≤ ( 1 2 + 𝑘 − 1 4 ⁢ 𝑟 − 2 ⁢ ( 𝑘 − 1 ) ) ⁢ 𝑛 . Moreover, we characterize the (infinite) family of graphs achieving equality in these lower and upper bounds. These results generalize known results for the domination and total domination numbers.