Reducing the domination number of graphs via edge contractions and vertex deletions
dc.contributor.author | Galby, Esther | |
dc.contributor.author | Lima, Paloma T. | |
dc.contributor.author | Ries, Bernard | |
dc.date.accessioned | 2022-04-04T10:22:02Z | |
dc.date.available | 2022-04-04T10:22:02Z | |
dc.date.created | 2022-01-17T11:13:22Z | |
dc.date.issued | 2021 | |
dc.identifier.issn | 0012-365X | |
dc.identifier.uri | https://hdl.handle.net/11250/2989507 | |
dc.description.abstract | In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k>0? We show that for k=1 (resp. k=2), the problem is NP-hard (resp. coNP-hard). We further prove that for k=1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input graph, and that it remains NP-hard when restricted to chordal {P6,P4+P2}-free graphs, bipartite graphs and {C3,…,Cℓ}-free graphs for any ℓ≥3. We also show that for k=1, the problem is coNP-hard on subcubic claw-free graphs, subcubic planar graphs and on 2P3-free graphs. On the positive side, we show that for any k≥1, the problem is polynomial-time solvable on (P5+pK1)-free graphs for any p≥0 and that it can be solved in FPT-time and XP-time when parameterized by treewidth and mim-width, respectively. Finally, we start the study of the problem of reducing the domination number of a graph via vertex deletions and edge additions and, in this case, present a complexity dichotomy on H-free graphs. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Elsevier | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Reducing the domination number of graphs via edge contractions and vertex deletions | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2020 The Author(s) | en_US |
dc.source.articlenumber | 112169 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1016/j.disc.2020.112169 | |
dc.identifier.cristin | 1982375 | |
dc.source.journal | Discrete Mathematics | en_US |
dc.identifier.citation | Discrete Mathematics. 2021, 344 (1), 112169. | en_US |
dc.source.volume | 344 | en_US |
dc.source.issue | 1 | en_US |
Tilhørende fil(er)
Denne innførselen finnes i følgende samling(er)
-
Department of Mathematics [932]
-
Registrations from Cristin [9489]