You are here

Total Domination in Graphs

Michael A. Henning and Anders Yeo
Publication Date: 
Number of Pages: 
Springer Monographs in Mathematics
[Reviewed by
Charles Ashbacher
, on

Given any graph G defined by a set of vertices V and edges E, a total dominating set TD is a subset of V such that every element of V is adjacent to an element of TD. There are several consequential definitions based on this, such as the minimal TD and the total domination number of G, defined as the minimum cardinality of the TD sets.

The book is written for graduate level courses where the students have a great deal of experience in graph theory. The first chapter is a review, which like most of the book could have the topic prefaced by the phrase “Recall that…” For an example of what I mean by that, think of a typical moment in treating integration techniques in second semester calculus: a complex integral will be put forward and the solution will begin with, “Recall the trig identity…” The authors use known results about graphs in the way we use trig identities in calculus.

The book is densely packed with theorems, few of which are followed by formal proofs. For example, chapter 11 has the title “Total Domination Critical Graphs” and is 18 pages long. There are 64 theorems/propositions/corollaries in that chapter along with 9 figures. In this respect, it is one of the most densely packed math books that I have ever encountered.

Yet the topic is thoroughly covered. If you are a graph theorist and are interested in learning about this important area of graph theory, then this is a book that will satisfy that need. The operational uses of total domination in computer networking based on centralized servers, networks of primary roads from key facilities and all other applications where all nodes must have a direct connection to a set of key nodes are obvious.

Charles Ashbacher splits his time between consulting with industry in projects involving math and computers, teaching college classes and co-editing The Journal of Recreational Mathematics. In his spare time, he reads about these things and helps his daughter in her lawn care business.


1. Introduction.- 2. Properties of Total Dominating Sets and General Bounds.- 3. Complexity and Algorithmic Results.- 4.Total Domination in Trees.- 5.Total Domination and Minimum Degree.- 6. Total Domination in Planar Graphs.- 7. Total Domination and Forbidden Cycles.- 8. Relating the Size and Total Domination Number.- 9. Total Domination in Claw-Free Graphs.- 10. Total Domination Number versus Matching Number.- 11. Total Domination Critical Graphs.- 12. Total Domination and Graph Products.- 13. Graphs with Disjoint Total Dominating Sets.- 14. Total Domination in Graphs with Diameter Two.- 15. Nordhaus-Gaddum Bounds for Total Domination.- 16. Upper Total Domination.- 17.Variations of Total Domination.- 18. Conjectures and Open Problems.- Index.