Deepak M. Bakal, Y. M. Borse, B. Waphare
2026.1.2International Journal of Computer Mathematics- Computer Systems Theory
Abstract
For an isolate-free graph G, let $ \gamma (G) $ γ(G), $ \gamma _t(G) $ γt(G), $ \gamma _{pr}(G) $ γpr(G), $ \gamma _{t2}(G) $ γt2(G) and $ \gamma _{pr2}(G) $ γpr2(G) denote domination number, total domination number, paired domination number, semitotal domination number and semipaired domination number, respectively. It is known that $ \gamma (G) \leq \gamma _{t2}(G) \leq \gamma _t(G) \leq \gamma _{pr}(G) $ γ(G)≤γt2(G)≤γt(G)≤γpr(G) and $ \gamma (G) \leq \gamma _{t2}(G) \leq \gamma _{pr2}(G) \leq \gamma _{pr}(G) $ γ(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.
Citation format
BAKAL, Deepak M.; BORSE, Y. M.; WAPHARE, B. Complexity of deciding the equality of domination parameters in chordal graphs. International Journal of Computer Mathematics- Computer Systems Theory, 2026, 11(1): 44–54.