Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647159 | Discrete Mathematics | 2015 | 8 Pages |
The domination number γ(G)γ(G), the total domination number γt(G)γt(G), the paired domination number γp(G)γp(G), the domatic number d(G)d(G), and the total domatic number dt(G)dt(G) of a graph GG without isolated vertices are related by trivial inequalities γ(G)≤γt(G)≤γp(G)≤2γ(G)γ(G)≤γt(G)≤γp(G)≤2γ(G) and dt(G)≤d(G)dt(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.