Reducing the domination number of graphs via edge contractions and vertex deletions
From MaRDI portal
Publication:2219962
DOI10.1016/j.disc.2020.112169zbMath1455.05055OpenAlexW3092286751MaRDI QIDQ2219962
Paloma T. Lima, Bernard Ries, Esther Galby
Publication date: 21 January 2021
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2020.112169
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (5)
Reducing the vertex cover number via edge contractions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Blocking total dominating sets via edge contractions ⋮ Reducing graph transversals via edge contractions ⋮ Using edge contractions to reduce the semitotal domination number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum \(d\)-blockers and \(d\)-transversals in graphs
- The most vital nodes with respect to independent set and vertex cover
- Dominating sets for split and bipartite graphs
- Domination dot-critical graphs
- Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
- Critical vertices and edges in \(H\)-free graphs
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Critical edges for the assignment problem: complexity and exact resolution
- Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
- Contraction Blockers for Graphs with Forbidden Induced Paths
- Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
- The Complexity of Multiterminal Cuts
- Minimum vertex blocker clique problem
- Vertex domination‐critical graphs
- Parameterized Algorithms
- Domination critical graphs
- Hard tiling problems with simple tiles
This page was built for publication: Reducing the domination number of graphs via edge contractions and vertex deletions
