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

DOI10.1016/J.DISC.2020.112169MaRDI QIDQ2219962zbMATH OpenOpenAlexFDO

Authors Paloma T. Lima, Bernard Ries, Esther Galby

Publication date 21 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.disc.2020.112169

zbMATH Keywords

blocker problemdomination numbergraph classesgraph modification problem

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (05C99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Reducing the domination number of ( P₃ + k P₂ )-free graphs via one edge contraction
• Reducing graph transversals via edge contractions
• The complexity of blocking (semi)total dominating sets with edge contractions
• Using edge contractions to reduce the semitotal domination number
• Blocking total dominating sets via edge contractions

Cites work

• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Critical edges for the assignment problem: complexity and exact resolution
• Critical vertices and edges in \(H\)-free graphs
• Dominating sets for split and bipartite graphs
• Domination and total domination contraction numbers of graphs.
• Domination critical graphs
• Domination dot-critical graphs
• Graph theory
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 6000604 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Minimum vertex blocker clique problem
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized algorithms
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Reducing the domination number of graphs via edge contractions
• The Complexity of Multiterminal Cuts
• The most vital nodes with respect to independent set and vertex cover
• Vertex domination‐critical graphs

Cited in

(16)

• The reduction of graph families closed under contraction
• Blocking total dominating sets via edge contractions
• Reducing graph transversals via edge contractions
• Using edge contractions to reduce the semitotal domination number
• Reducing the domination number of ( P₃ + k P₂ )-free graphs via one edge contraction
• The complexity of blocking (semi)total dominating sets with edge contractions
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• Blocking independent sets for \(H\)-free graphs via edge contractions and vertex deletions
• Reducing graph transversals via edge contractions
• Reducing the domination number of graphs via edge contractions
• Reducing the vertex cover number via edge contractions
• On blockers and transversals of maximum independent sets in co-comparability graphs
• Distance-preserving graph compression techniques
• The complexity of blocking all solutions
• Finding induced subgraphs from graphs with small mim-width

This page was built for publication: Reducing the domination number of graphs via edge contractions and vertex deletions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2219962)