Journal article

Blocking Total Dominating Sets Via Edge Contractions

    2021
Published in:
  • Theoretical Computer Science. - Elsevier. - 2021, vol. 877, p. 18-35
English In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-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.
Faculty
Faculté des sciences économiques et sociales
Department
Département d'informatique
Language
  • English
Classification
Computer science
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/309575
Statistics

Document views: 13 File downloads:
  • 2021_Galby_Blocking.pdf: 3