Using edge contractions to reduce the semitotal domination number

Galby, Esther; Lima, Paloma T.; Mann, Felix; Ries, Bernard

doi:10.1016/j.tcs.2022.10.020

Back

Journal article

Using edge contractions to reduce the semitotal domination number

BP2-STS

Galby, Esther CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Lima, Paloma T. IT University of Copenhagen, Copenhagen, Denmark
Mann, Felix University of Fribourg, Switzerland
Ries, Bernard ORCID University of Fribourg, Fribourg, Switzerland

21.10.2022

Published in:

Theoretical Computer Science. - Elsevier BV. - 2023, vol. 939, p. 140-160

English In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting kedges, 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.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language