Reducing the domination number of graphs via edge contractions

DOI10.4230/LIPICS.MFCS.2019.41MaRDI QIDQ5092403zbMATH OpenFDO

Authors Esther Galby, Bernard Ries, Paloma T. Lima

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1903.01800

zbMATH Keywords

blocker problemdomination numbergraph classes

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Reducing the domination number of graphs via edge contractions and vertex deletions
• Reducing the domination number of ( P₃ + k P₂ )-free graphs via one edge contraction
• Using edge contractions to reduce the semitotal domination number
• The complexity of blocking (semi)total dominating sets with edge contractions
• 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.
• Graph theory
• scientific article; zbMATH DE number 6000604 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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
• The most vital nodes with respect to independent set and vertex cover
• The point-set embeddability problem for plane graphs

Cited in

(9)

• The reduction of graph families closed under contraction
• Complexity and algorithms for constant diameter augmentation problems
• Reducing the domination number of graphs via edge contractions and vertex deletions
• 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
• Reducing graph transversals via edge contractions
• Reducing the domination number of graphs via edge contractions

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

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