An upper bound on the 2-outer-independent domination number of a tree
Marcin Krzywkowski · Comptes Rendus Mathématique · 2011
A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V ( G ) ∖ D has at least two neighbors in D , and the set V ( G ) ∖ D is independent. The 2-outer-independent domination number of a graph G , denoted by γ 2 oi ( G ) , is the minimum cardinality of a 2-outer-independent dominating set of G . We prove that for every nontrivial tree T of order n with l leaves we have γ 2 oi ( T ) ⩽ ( n + l ) / 2 , and we characterize the trees attaining this upper bound.