scientific article; zbMATH DE number 1095171
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.
- Dominant vertices in regulatory networks dynamics
- Efficiency in exponential time for domination-type problems
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Efficient edge domination in regular graphs
- On the domination numbers of generalized de Bruijn digraphs and generalized Kautz digraphs
- Domination subdivision numbers of trees
- An upper bound on the domination number of a graph with minimum degree 2
- On signed cycle domination in graphs
- Minimum partition of an independence system into independent sets
- \(k\)-tuple domination in graphs
- Perfect r-domination in the Kronecker product of two cycles, with an application to diagonal/toroidal mesh
- Paired-domination in \(P_{5}\)-free graphs
- Total domination in graphs with given girth
- Silver cubes
- Roman domination in regular graphs
- Complete description of forbidden subgraphs in the structural domination problem
- On the ratios between packing and domination parameters of a graph
- The exact domination number of the generalized Petersen graphs
- A note on dominating sets and average distance
- Minimum fractional dominating functions and maximum fractional packing functions
- On the Roman domination number of a graph
- An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm
- The signed domatic number of some regular graphs
- On total domination vertex critical graphs of high connectivity
- Vertex and edge covers with clustering properties: Complexity and algorithms
- Up- and downgrading the 1-center in a network
- Upper bounds on the \(k\)-domination number and the \(k\)-Roman domination number
- Upper bounds on the upper signed total domination number of graphs
- Average distances and distance domination numbers
- On identifying codes in the hexagonal mesh
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Feedback vertex sets in star graphs
- On the profile of the corona of two graphs
- Parameterized computational complexity of control problems in voting systems
- Constructive characterizations of \( (\gamma_p,\gamma)\)-and \( (\gamma_p, \gamma_{pr})\)-trees
- Some remarks on the signed domatic number of graphs with small minimum degree
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Distance paired-domination problems on subclasses of chordal graphs
- A randomized algorithm for determining dominating sets in graphs of maximum degree five
- Total domination in partitioned graphs
- Total restrained domination in cubic graphs
- On certain spanning subgraphs of embeddings with applications to domination
- Total domination in planar graphs of diameter two
- Connected k-tuple twin domination in de Bruijn and Kautz digraphs
- Radial trees
- A survey of stratified domination in graphs
- Secure domination critical graphs
- Domination with exponential decay
- Liar's domination in graphs
- On global domination critical graphs
- Remarks about disjoint dominating sets
- An independent dominating set in the complement of a minimum dominating set of a tree
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- On the out-domination and in-domination numbers of a digraph
- Graphs with large restrained domination number
- Minus domination in graphs
- Real and integer domination in graphs
- On perfect neighborhood sets in graphs
- On the differences between the upper irredundance, upper domination and independence numbers of a graph
- Weighted efficient domination problem on some perfect graphs
- Nordhaus--Gaddum bounds for independent domination
- Efficient minus and signed domination in graphs
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Lower bounds on the minus domination and \(k\)-subdomination numbers.
- Efficient dominating sets in Cayley graphs.
- On \(\alpha_{r}\gamma_{s}(k)\)-perfect graphs
- Defending the Roman Empire from multiple attacks
- Stratification and domination in graphs
- Edge-recognizable domination numbers.
- Changing and unchanging domination: A classification
- \(H\)-domination in graphs
- On the identification problems in products of cycles
- Extremal connected graphs for independent domination number
- Relations between the lower domination parameters and the chromatic number of a graph.
- On upper domination Ramsey numbers for graphs.
- On connected k-domination numbers of graphs.
- On \(i^{-}\)-ER-critical graphs
- Minus domination number in \(k\)-partite graphs.
- Roman domination in graphs.
- Iterated colorings of graphs.
- Signed total domination in graphs.
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- On the distribution of the domination number for random class cover catch digraphs
- Closure systems and their structure
- Perfect edge domination and efficient edge domination in graphs
- Graphs having distance-\(n\) domination number half their order
- An upper bound for the minimum number of queens covering the \(n {\times} n\) chessboard
- Neighborhood contraction in graphs
- Connected \(k\)-dominating graphs
- On upper transversals in 3-uniform hypergraphs
- Nordhaus-Gaddum problems for power domination
- Domination in intersecting hypergraphs
- Enumeration of maximal irredundant sets for claw-free graphs
- Predicting protein-protein interactions using graph invariants and a neural network
- Domination in some subclasses of bipartite graphs
- Some progress on the double Roman domination in graphs
- The weakly connected independent set polytope in corona and join of graphs
- Computing a minimum paired-dominating set in strongly orderable graphs
- On approximating (connected) 2-edge dominating set by a tree
- On the game total domination number
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4368728)