Connected domination versus dominating sets inducing large components

A dominating set in a graph G is a set D of vertices of G such that every vertex in V ( G ) ∖ D has a neighbor in D , where two vertices are neighbors if they are adjacent. Further, if the subgraph G [ D ] induced by D is a connected graph, then D is a connected dominating set of G . The connected domination number of G , denoted γ c ( G ) , is the minimum cardinality among all connected dominating sets of G . For k ≥ 1 an integer, the k -component domination number γ k ( G ) , first defined by Alvarado et al. (2016) [2] , is the minimum cardinality among all dominating sets D of G such that every component in G [ D ] has order at least k . We note that k -component domination is a natural generalization of both domination and total domination as γ 1 ( G ) = γ ( G ) and γ 2 ( G ) = γ t ( G ) , where γ ( G ) is the domination number of G and γ t ( G ) is the total domination number of G . We show that for k ≥ 1 if G is a connected graph of order at least k , then γ c ( G ) ≤ ( k + 2 k ) γ k ( G ) − 2 , and this bound is tight for all k ≥ 1 . This bound generalizes a 1982 result due to Duchet and Meyniel (when k = 1 ) and a 1991 result due to Favaron and Kratsch (when k = 2 ). We characterize the trees T of order at least k satisfying γ c ( T ) = ( k + 2 k ) γ k ( T ) − 2 .