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

DOI10.1016/J.DISC.2020.112169zbMATH Open1455.05055OpenAlexW3092286751MaRDI QIDQ2219962FDOQ2219962

Authors: 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

Recommendations

• Reducing the domination number of \(( P_3 + k P_2 )\)-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

zbMATH Keywords

domination numbergraph classesgraph modification problemblocker problem

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• The Complexity of Multiterminal Cuts
• Parameterized algorithms
• Domination critical graphs
• Domination dot-critical graphs
• Hard tiling problems with simple tiles
• Dominating sets for split and bipartite graphs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The most vital nodes with respect to independent set and vertex cover
• Minimum vertex blocker clique problem
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Vertex domination‐critical graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Critical vertices and edges in \(H\)-free graphs
• 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
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Critical edges for the assignment problem: complexity and exact resolution
• Domination and total domination contraction numbers of graphs.
• Title not available (Why is that?)

Cited In (13)

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

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)