ABSTRACT
In general, when studying subsets of a given type, we are interested in finding either a smallest or a largest such set in a graph. For instance, one considers such problems as finding the minimum cardinality of a dominating set or a cover, or finding the maximum cardinality of an independent set or a packing. Since most of these subset problems are NP-complete for arbitrary graphs, it is natural to find bounds for these numbers. In this chapter, we describe bounds for the domination number !(G). Additional bounds will be supplied throughout the text, particularly Chapter 3. Algorithmic problems associated with actually finding subsets with the desired properties will be discussed in Chapter 12.
