Blocking total dominating sets via edge contractions

DOI10.1016/j.tcs.2021.03.028zbMath1478.68239arXiv2009.08806OpenAlexW3152137366MaRDI QIDQ2034793

F. Mann, Bernard Ries, Esther Galby

Publication date: 23 June 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitytotal dominating setedge contraction\(H\)-free graphsblocker problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

In memory of Jérôme Monnot ⋮ Using edge contractions and vertex deletions to reduce the independence number and the clique number ⋮ Reducing the vertex cover number via edge contractions ⋮ Reducing graph parameters by contractions and deletions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Using edge contractions to reduce the semitotal domination number

Cites Work

• 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
• 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
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• 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
• Minimum vertex blocker clique problem
• Efficient algorithms for graphs with few \(P_4\)'s
• Hard tiling problems with simple tiles

This page was built for publication: Blocking total dominating sets via edge contractions