Reducing the domination number of (P3+kP2)-free graphs via one edge contraction

Galby, Esther; Mann, Felix; Ries, Bernard

doi:10.1016/j.dam.2021.09.009

Back

Journal article

Reducing the domination number of (P3+kP2)-free graphs via one edge contraction

BP2-STS

Galby, Esther CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Mann, Felix ORCID University of Fribourg, Department of Informatics, Fribourg, Switzerland
Ries, Bernard ORCID University of Fribourg, Department of Informatics, Fribourg, Switzerland

23.09.2021

Published in:

Discrete Applied Mathematics. - Elsevier BV. - 2021, vol. 305, p. 205-210

Discrete Mathematics and Combinatorics

English 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 (P3 + kP2)-free graphs for any k ≥ 0 which can be combined with former results to obtain a complexity dichotomy of the problem on H-free graphs.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language