Perfectly relating the domination, total domination, and paired domination numbers of a graph

摘要

The domination number gamma(G), the total domination number gamma(t)(G), the paired domination number gamma(p)(G), the domatic number d(G), and the total domatic number d(t)(G) of a graph G without isolated vertices are related by trivial inequalities gamma(G) <= gamma(t) G) <= gamma(p)(G) <= 2 gamma(G) and d(t) (G) <= d(G). Very little is known about the graphs that satisfy one of these inequalities with equality. We study classes of graphs defined by requiring equality in one of the above inequalities for all induced subgraphs that have no isolated vertices and whose domination number is not too small. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs. Furthermore, we prove some hardness results, which suggest that the extremal graphs for some of the above inequalities do not have a simple structure. (C) 2015 Elsevier B.V. All rights reserved.