Complexity of Deciding the Equality of Domination Parameters in Chordal Graphs

For an isolate-free graph G, let γ(G), γt(G), γpr(G), γt2(G) and γpr2(G) denote domination number, total domination number, paired domination number, semitotal domination number and semipaired domination number, respectively. It is known that γ(G)≤γt2(G)≤γt(G)≤γpr(G) and γ(G)≤γt2(G)≤γpr2(G)≤γpr(G). Several papers have investigated the complexity of deciding whether a graph attains equality within the above inequalities in general graphs and restricted graph classes such as bipartite graphs and planar graphs. However, the recognition complexity of these equalities in chordal graphs remains open in the literature. In this paper, we address this gap by proving that the decision problem corresponding to each of the above equalities is NP-hard, even when restricted to chordal graphs.MSC: 05C69, 68Q17