ABSTRACT
One of the fastest growing areas within graph theory is the study of domination and related subset problems such as independence, irredundance, and matching. The origin of the study of dominating sets in graphs is the following problem of dominating queens: What is the minimum number of queens to be placed on an n×n chessboard in such a way that every cell in the board is either occupied by a queen or dominated by a queen, where a queen dominates all those cells that can be reached in a single move? This number is the domination number of the graph G whose vertex set V is the set of n2 cells of the n×n board and two vertices i and j are adjacent if the queen at i can reach j in a single move. The term domination was first introduced by Ore [1]. Domination and its several variants serve as natural models for many optimization problems. Domination theory has many and varied applications in diverse areas such as design and analysis of communication networks, social network theory, routing problems, kernels of games, operations research, bioinformatics, computational complexity, algorithm design, linear algebra, and optimization. The publication of a survey article by Cockayne and Hedetniemi [2] in 1977, led to the modern study of domination in graphs. Since then more than 1500 papers have been published on this topic. A comprehensive treatment of the fundamentals of domination is given in the book by Haynes et al. [3] and surveys of several advanced topics can be found in the book edited by Haynes et al. [4]. In this chapter
we present some of the basic results in domination, recent developments, and directions for further research.
