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
Normal 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
    0 references
    0 references
    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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references