Reducing the domination number of graphs via edge contractions and vertex deletions

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

zbMATH Keywords

domination numbergraph classesgraph modification problemblocker problem

Mathematics Subject Classification ID

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