Blocking total dominating sets via edge contractions

DOI10.1016/J.TCS.2021.03.028MaRDI QIDQ2034793zbMATH OpenOpenAlexFDO

Authors F. Mann, Bernard Ries, Esther Galby

Publication date 23 June 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

\(H\)-free graphsblocker problemcomputational complexityedge contractiontotal dominating set

Mathematics Subject Classification ID

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

Abstract: In this paper, we study the problem of deciding whether the total domination number of a given graph $G$ can be reduced using exactly one edge contraction (called 1-Edge Contraction($gamm{a}_t$)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete dichotomy for $H$-free graphs.

Recommendations

• The complexity of blocking (semi)total dominating sets with 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
• Domination and total domination contraction numbers of graphs.

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
• Domination and total domination contraction numbers of graphs.
• Efficient algorithms for graphs with few P₄'s
• Graph theory
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 6000604 (Why is no real title available?)
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• Minimum vertex blocker clique problem
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• 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
• The most vital nodes with respect to independent set and vertex cover

Cited in

(15)

• Using edge contractions to reduce the semitotal domination number
• In memory of Jérôme Monnot
• Using edge contractions and vertex deletions to reduce the independence number and the clique number
• 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
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs
• Contraction Blockers for Graphs with Forbidden Induced Paths
• Domination and total domination contraction numbers of graphs.
• Reducing the domination number of graphs via edge contractions
• scientific article; zbMATH DE number 7650254 (Why is no real title available?)
• Reducing the vertex cover number via edge contractions
• Reducing graph parameters by contractions and deletions
• On blockers and transversals of maximum independent sets in co-comparability graphs
• Distance-preserving graph compression techniques

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

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