Fundamentals of domination in graphs. (English) Zbl 0890.05002

Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J.

Pure and Applied Mathematics, Marcel Dekker. 208. New York, NY: Marcel Dekker, Inc. xi, 446 p. (1998).

The theory of domination in graphs is an evergreen of graph theory. It started from the recreational chessboard problems of W. Rouse-Ball in the past century. Since that time it has been steadily developing and has many applications in mathematics (e.g. coding theory) and in practical life. The basic concept is the notion of dominating set in a graph. A subset \(D\) of the vertex set \(V(G)\) of an undirected graph \(G\) is called dominating in \(G\), if each vertex of \(G\) either belongs to \(D\), or is adjacent to a vertex of \(D\).
This book gives a rich survey of results concerning domination in graphs. It has twelve chapters which are preceded not only by the Preface, but also by the Prolegomenon in which basic concepts of graph theory are described and motivation for the study of domination is shown. The first chapter, Introduction, lists some applications of this study; among them there are chessboard problems, but also quite practical applications, e.g., radio stations, computers, computational networks, etc. In the second chapter, Bounds on the domination number, the concept of domination number is introduced (the minimum number of vertices of a dominating set) and various inequalities relating it to other numerical invariants of graphs are presented. In the third chapter, Domination, independence and irredundance, the interrelations between dominating sets and other important sets, namely independent sets and irredundant sets, are studied. The domination chain \[ \text{ir}(G)\leq\gamma(G)\leq i(G)\leq\beta_0(G)\leq\Gamma(G)\leq\text{IR}(G) \] containing irredundance, domination, independent domination, vertex independence, upper domination and upper irredundance numbers, is presented and discussed. (This chain is also in the dedication of this book to E. J. Cockayne.) Special properties of dominating sets are treated in the fourth chapter: Efficiency, redundancy, and their duals. Special attention is paid to codes and cubes and to the closed neighbourhood order domination. The fifth chapter, Changing and unchanging domination, studies the equations, how the numerical invariants of graphs related to domination may be changed at slight changes of the graph, e.g., at deleting an edge or a vertex. The sixth chapter, Conditions on the dominating set, treats additional conditions imposed to a dominating set, e.g., to be independent, to induce a connected subgraph, to induce a complete subgraph. The seventh chapter, Varieties of domination, studies properties of sets which are variations of the property of being dominating; e.g., multiple domination, distance domination, strong domination, etc. (For example, a subset \(D\) of \(V(G)\) is strongly dominating, if each vertex of \(G\)—including the vertices of \(D\)—is adjacent to a vertex of \(D\).) In the eighth chapter, Multiproperty and multiset parameters, more dominating sets in a graph are considered. Especially the domatic number of \(G\) is introduced, which is the maximum number of classes of a partition of \(V(G)\) into dominating sets. Its relation to the domination number is the same as that of the chromatic number to the independence number. The content of the ninth chapter is evident from its title “Sums and products of parameters”. Among the results, Nordhaus-Gaddum type results are presented, i.e., bounds for the sum or the product of the value of a certain numerical invariant of a graph \(G\) and of its complement \(\overline G\). The domination number can be defined also from another viewpoint—by means of dominating functions on a graph. These functions may have various variations, and they are the content of the tenth chapter: Dominating functions. The eleventh chapter, Frameworks for domination, shows how domination in graphs can be applied to other branches of mathematics, e.g., to linear programming. The computational complexity of the problems concerning domination is the topic of the twelfth chapter: Domination complexity and algorithms. The book contains also an appendix which gives a survey of numerical invariants of graphs which concern domination. A bibliography follows; it contains more than 1200 titles.
The book brings much useful information about domination in graphs and is written intelligibly. Such advanced monographs on special parts of graph theory are very useful now, at the time of information explosion, because it enables the reader to save the time which otherwise he would have spent by reading hundreds of original papers. The more such books, the better. I have found only one mistake: in the notation list read “vertex independence number” instead of “vertex independent number”. I appreciate the fantasy at creating the terminology; on page 51 a graph is named “wounded spider”. The book may be recommended to all seriously interested in graph theory and already having some knowledge of it.

Reviewer: B.Zelinka (Liberec)

MSC:

05-02	Research exposition (monographs, survey articles) pertaining to combinatorics
05C35	Extremal problems in graph theory
05C75	Structural characterization of families of graphs

Keywords:

dominating set; survey; domination; domination number; independent sets; irredundant sets; invariants of graphs; domatic number; dominating functions