Back
p3kp2_0
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
Applied Mathematics
Discrete Mathematics and Combinatorics
Domination
Edge contraction
Graph theory
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
  • English
Classification
Computer science and technology
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/322005
Statistics
Document views: 26 File downloads:
  • p3kp2_0.pdf: 71