Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction (Q2235275): Difference between revisions

In this paper, the authors reduce the domination number of $G$ using only one edge contraction. The main result shows that the problem is polynomial-time solvable on $( P_3 + k P_2 )$-free graphs for any $k\geq 0$ which can be combined with former results to obtain a complexity dichotomy of the problem on $H$-free graphs. Moreover, the authors present an algorithm which determines in polynomial time whether $G$ is a Yes-instance of 1-Edge Contraction $(\gamma)$ or not.