Reducing the domination number of P_3+kP_2-free graphs via one edge contraction

10/27/2020
by   Esther Galby, et al.
0

In this note, we consider the following problem: given a connected graph G, can we reduce the domination number of G by using only one edge contraction? We show that the problem is polynomial-time solvable on P_3+kP_2-free graphs for any k ≥ 0 which combined with results of [1,2] leads to a complexity dichotomy of the problem on H-free graphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset