Advanced Graph Theory ResearchInterconnection Networks and SystemsMarkov Chains and Monte Carlo Methods

Deepak M. Bakal, Y. M. Borse, B. Waphare

2026.1.2International Journal of Computer Mathematics- Computer Systems Theory

DOI: 10.1080/23799927.2026.2629390

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.