Reducing the domination number of graphs via edge contractions and vertex deletions
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/2989507/lima%2b2021.pdf.jpg?sequence=6&isAllowed=y)
Åpne
Permanent lenke
https://hdl.handle.net/11250/2989507Utgivelsesdato
2021Metadata
Vis full innførselSamlinger
- Department of Mathematics [968]
- Registrations from Cristin [10237]
Sammendrag
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.