Domination alteration sets in graphs

Abstract

The domination number [alpha](G) of a graph G is the size of a minimum dominating set, i.e., a set of points with the property that every other point is adjacent to a point of the set. In general [alpha](G) can be made to increase or decrease by the removal of points from G. Our main objective is the study of this phenomenon. For example we show that if T is a tree with at least three points then [alpha](T - v) > [alpha] (T) if and only if [nu] is in every minimum dominating set of T. Removal of a set of lines from a graph G cannot decrease the domination number. We obtain some upper bounds on the size of a minimum set of lines which when removed from G increases the domination number.