Semitotal Domination: New hardness results and a polynomialtime algorithm for graphs of bounded mimwidth Abstract   A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size      xcexb3    t  2    (  G  )    of a semitotal dominating set of G is squeezed between the domination number    xcexb3  (  G  )    and the total domination number      xcexb3    t    (  G  )   .   Semitotal Dominating Set  is the problem of finding, given a graph G, a semitotal dominating set of G of size      xcexb3    t  2    (  G  )   . In this paper, we continue the systematic study on the computational complexity of this problem when restricted to special graph classes. In particular, we show that it is solvable in polynomial time for the class of graphs of bounded mimwidth by a reduction to  Total Dominating Set  and we provide several approximation lower bounds for subclasses of subcubic graphs. Moreover, we obtain complexity dichotomies in monogenic classes for the decision versions of  Semitotal Dominating Set  and  Total Dominating Set .  Finally, we show that it is    NP   complete to recognise the graphs such that      xcexb3    t  2    (  G  )      xcexb3    t    (  G  )    and those such that    xcexb3  (  G  )      xcexb3    t  2    (  G  )   , even if restricted to be planar and with maximum degree at most 4, and we provide forbidden induced subgraph characterisations for the graphs heriditarily satisfying either of these two equalities.

Independent domination versus weighted independent domination Abstract    Independent domination  is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. Trying to better understand the gap between the two versions of the problem, in the present paper we prove two complexity results. First, we extend NPhardness of the weighted version in a certain class to the unweighted case. Second, we strengthen polynomialtime solvability of the unweighted version in the class of      P    2        P    3     free graphs to the weighted case. This result is tight in the sense that both versions are NPhard in the class of      P    3        P    3     free graphs, i.e.      P    3        P    3      is a minimal graph forbidding of which produces an NPhard case for both versions of the problem.