Reducing the domination number of graphs via edge contractions

Abstract

In this paper, we study the following problem: given a connected graph $G$, can we reduce the domination number of $G$ by at least one using $k$ edge contractions, for some fixed integer $k\ge 0$? We present positive and negative results regarding the computational complexity of this problem.