2019/06/28 by Esther Galby, Paloma T. Lima, Galby, Esther +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1906.12297
In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to \P6,P4+P2\-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected.