A lower bound on the total outer-independent domination number of a tree
Marcin Krzywkowski · Comptes Rendus Mathématique · 2010
A total outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbour in D , and the set V ( G ) ∖ D is independent. The total outer-independent domination number of a graph G , denoted by γ t o i ( G ) , is the minimum cardinality of the total outer-independent dominating set of G . We prove that for every nontrivial tree T of order n with l leaves we have γ t o i ( T ) ⩾ ( 2 n − 2 l + 2 ) / 3 , and we characterize the trees attaining this lower bound.