Abstract We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter $$\pi $$ π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed $$d=1$$ d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in $$(C_3+P_1)$$ ( C 3 + P 1 ) -free graphs even for fixed $$d=1$$ d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023 ).

In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k≥1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k=1 and obtain in particular a complete complexity dichotomy for monogenic classes.

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 (P3+kP2)-free graphs for any k≥0 which can be combined with former results to obtain a complexity dichotomy of the problem on H-free graphs.

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 complexity dichotomy for H-free graphs.