Reducing the domination number of P₃+kP₂-free graphs via one edge contraction

2020/10/27 by Galby, Esther, Mann, Felix, Ries, Bernard
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.14155

Abstract

In this note, we consider the following problem: given a connected graph G, can we reduce the domination number of G by using only one edge contraction? We show that the problem is polynomial-time solvable on P₃+kP₂-free graphs for any k ≥ 0 which combined with results of [1,2] leads to a complexity dichotomy of the problem on H-free graphs.

Related

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