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

被引：5

作者：

Galby, E. ^{[1
]}

Mann, F. ^{[2
]}

Ries, B. ^{[2
]}

机构：

[1] CISPA Helmholtz Ctr Informat Secur, Saarbrucken, Germany

[2] Univ Fribourg, Dept Informat, Fribourg, Switzerland

来源：

DISCRETE APPLIED MATHEMATICS | 2021年 / 305卷

关键词：

Domination; Edge contraction; Graph theory;

D O I：

10.1016/j.dam.2021.09.009

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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-3 + kP(2))-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. (c) 2021 The Author(s). Published by Elsevier B.V.

引用

页码：205 / 210

页数：6