Blocking total dominating sets via edge contractions

2020/09/18 by Galby, Esther, Mann, Felix, Ries, Bernard
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2009.08806

Abstract

In this paper, we study the problem of deciding whether the total domination number of a given graph G can be reduced using exactly one edge contraction (called 1-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 dichotomy for H-free graphs.

Related

• Reducing the domination number of graphs via edge contractions
• The complexity of blocking (semi)total dominating sets with edge contractions
• The complexity of blocking (semi)total dominating sets with edge contractions
• Blocking dominating sets for H-free graphs via edge contractions
• Using edge contractions to reduce the semitotal domination number