Using edge contractions to reduce the semitotal domination number

Esther Galby, Paloma Thomé de Lima, Felix Mann, Bernard Ries

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstract

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.
OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind939
ISSN0304-3975
DOI
StatusUdgivet - 2023

Emneord

  • Blocker problem
  • Edge contraction
  • Semitotal domination

Fingeraftryk

Dyk ned i forskningsemnerne om 'Using edge contractions to reduce the semitotal domination number'. Sammen danner de et unikt fingeraftryk.

Citationsformater