A new lower bound for the independent domination number of a tree

Abstract

A set D of vertices in a graph G is an independent dominating set of G if D is an independent set and every vertex not in D is adjacent to a vertex in D. The independent domination number of G, denoted by i(G), is the minimum cardinality among all independent dominating sets of G. In this paper we show that if T is a nontrivial tree, then i(T) ≥ n(T)+γ(T)−l(T)+2/4, where n(T), γ(T) and l(T) represent the order, the domination number and the number of leaves of T, respectively. In addition, we characterize the trees achieving this new lower bound.