Publisher DOI: 10.1016/j.tcs.2022.12.028
Title: The complexity of blocking (semi)total dominating sets with edge contractions
Language: English
Authors: Galby, Esther 
Keywords: Blocker problem; Edge contraction; H-free graphs; Semitotal domination number; Total domination number
Issue Date: 13-Jan-2023
Publisher: Elsevier
Source: Theoretical Computer Science (2023)
Abstract (english): 
We consider the problem of reducing the (semi)total domination number of a graph by one by contracting edges. It is known that this can always be done with at most three edge contractions and that deciding whether one edge contraction suffices is an NP-hard problem. We show that for every fixed k∈2,3, deciding whether exactly k edge contractions are necessary is NP-hard and further provide for k=2 complete complexity dichotomies on monogenic graph classes.
ISSN: 0304-3975
Journal: Theoretical computer science 
Institute: Algorithmen und Komplexität E-11 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.