Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction (Q2235275): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1016/j.dam.2021.09.009 / rank | |||
Property / DOI | |||
Property / DOI: 10.1016/J.DAM.2021.09.009 / rank | |||
Normal rank |
Latest revision as of 14:53, 17 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction |
scientific article |
Statements
Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction (English)
0 references
21 October 2021
0 references
In this paper, the authors reduce the domination number of $G$ using only one edge contraction. The main result shows that the problem is polynomial-time solvable on $( P_3 + k P_2 )$-free graphs for any $k\geq 0$ which can be combined with former results to obtain a complexity dichotomy of the problem on $H$-free graphs. Moreover, the authors present an algorithm which determines in polynomial time whether $G$ is a Yes-instance of 1-Edge Contraction $(\gamma)$ or not.
0 references
domination
0 references
edge contraction
0 references