Back to Search Start Over

Reducing the domination number of $P_3+kP_2$-free graphs via one edge contraction

Authors :
Galby, Esther
Mann, Felix
Ries, Bernard
Publication Year :
2020
Publisher :
arXiv, 2020.

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_3+kP_2$-free graphs for any $k \geq 0$ which combined with results of [1,2] leads to a complexity dichotomy of the problem on $H$-free graphs.

Details

Database :
OpenAIRE
Accession number :
edsair.doi.dedup.....2adea60328073c574479f50d29b53e7e
Full Text :
https://doi.org/10.48550/arxiv.2010.14155