Complexity of Computing of The Domination Number in Hereditary Classes of Graphs

Abstract

Let \(\gamma(G)\) be the domination number of a graph \(G\). A class \(\mathcal{P}\) of graphs is called \(\gamma\)-complete if the problem of determining \(\gamma(G)\), \(G \in \mathcal{P}\), is NP-complete. A class \(\mathcal{P}\) of graphs is called \(\gamma\)-polynomial if there is a polynomial-time algorithm for calculating \(\gamma(G)\) for all graphs \(G \in \mathcal{P}\).

We denote \(\Gamma = \{P_k\cap nK_1 : k \leq 4 \text{ and } n \geq 0\}\). Korobitsin \([4]\) proved that if \(\mathcal{P}\) is a hereditary class defined by a unique forbidden induced subgraph \(H\), then

1. when \(H \in \Gamma\), \(\mathcal{P}\) is a \(\gamma\)-polynomial class,
2. when \(H \notin \Gamma\), \(\mathcal{P}\) is a \(\gamma\)-complete class.

We extend a positive result (i) in the following way. The class \(\Gamma\) is hereditary, and it is characterized by the set

\[Z(\Gamma) = \{2K_2, K_{1,3},C_3,C_4,C_5\}\]

of minimal forbidden induced subgraphs.

For each \(Z \subseteq Z(\Gamma)\) we consider a hereditary class \({FIS}(Z)\) defined by the set \(Z\) of minimal forbidden induced subgraphs. We prove that \(\mathcal{FIS}(Z)\) is \(\gamma\)-complete in 16 cases, and it is \(\gamma\)-polynomial in the other 16 cases. We also prove that \(2K_2\)-free graphs with bounded clique number constitute a \(\gamma\)-polynomial class.