Ergebnisse einschränken

Blocking Total Dominating Sets Via Edge Contractions

Galby, Esther ; Mann, Felix ; Ries, Bernard

In: Theoretical Computer Science, 2021, vol. 877, p. 18-35

In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-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 complexity dichotomy for H-free graphs.