Calculating the domination number is an NPHard problem. Does it remain NPHard if we restrict it to nonbipartite graphs?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The general case of the domination number problem reduces to the nonbipartite case. Given a (possibly bipartite graph) $G$, create new graph $G'$ consisting of an copy of $G$ and a disjoint copy of $K_3$. The domination number of the new (nonbipartite) graph $G'$ is exactly one more than that of the original graph $G$. So computing the domination number of the new graph $G'$ is exactly as hard as computing that of the original graph $G$. 

