Using edge contractions to reduce the semitotal domination number

DOI10.1016/j.tcs.2022.10.020zbMath1502.05187arXiv2107.03755OpenAlexW3180032410MaRDI QIDQ2098176

F. Mann, Paloma T. Lima, Bernard Ries, Esther Galby

Publication date: 17 November 2022

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

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

zbMATH Keywords

edge contractionsemitotal dominationblocker problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Reducing the vertex cover number via edge contractions

Cites Work

• Unnamed Item
• Unnamed Item
• Minimum edge blocker dominating set problem
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Matching interdiction
• Blockers for simple Hamiltonian paths in convex geometric graphs of even order
• Nonempty intersection of longest paths in series-parallel graphs
• Network flow interdiction on planar graphs
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• The node-deletion problem for hereditary properties is NP-complete
• Exact algorithms for the minimum cost vertex blocker clique problem
• Critical vertices and edges in \(H\)-free graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Blocking total dominating sets via edge contractions
• Reducing graph transversals via edge contractions
• Reducing the domination number of graphs via edge contractions and vertex deletions
• Reducing the domination number of \(( P_3 + k P_2 )\)-free graphs via one edge contraction
• Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
• 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
• Transversals of Longest Paths and Cycles
• The complexity of satisfiability problems
• Hard tiling problems with simple tiles

This page was built for publication: Using edge contractions to reduce the semitotal domination number