论文标题
通过一个边缘收缩减少$ P_3+KP_2 $的支配数
Reducing the domination number of $P_3+kP_2$-free graphs via one edge contraction
论文作者
论文摘要
在本说明中，我们考虑以下问题：给定连接的图形$ g $，我们可以仅使用一个边缘收缩来减少$ g $的支配数吗？我们表明，问题是在$ p_3+kp_2 $ - 任何$ k \ geq 0 $的$ p_3+kp_2 $ free Graphs上的多项式时间溶液，与[1,2]的结果结合在一起，导致了$ H $ Free图的复杂性二分法。
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.
