Blocking total dominating sets via edge contractions

09/18/2020
by   Esther Galby, et al.
0

In this paper, we study the problem of deciding whether the total domination number of a given graph G can be reduced using exactly one edge contraction (called 1-Edge Contraction(γ_t)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete dichotomy for H-free graphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset