Back to Search
Start Over
Reducing the domination number of $P_3+kP_2$-free graphs via one edge contraction
- 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