The semitotal domination problem in block graphs
type: Item
instance of: scholarly article
title: The semitotal domination problem in block graphs
zbMATH Open document ID: 1484.05155
author: Yanyan Li
publication date: 2022-01-03T00:00:00Z
review text: In this paper, the authors studied the semitotal dominating set in block graphs. Firstly, they considered the complexity of finding a minimum semi-TD-set in block graphs and presented the linear time algorithm for computing a minimum semitotal dominating set. Moreover, they have shown the semitotal domination problem remains NP-complete for undirected path graphs which is a subclass of chordal graphs. These studies are interesting to explore the complexity of finding a minimum semitotal dominating set of strongly chordal graphs
reviewed by: Thanin Sitthiwirattham
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C51
zbMATH DE Number: 7451250
zbMATH Keywords: domination
zbMATH Keywords: semitotal domination
zbMATH Keywords: block graphs
zbMATH Keywords: undirected path graphs
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
full work available at URL: dmgt.2254
OpenAlex ID: W2983858766
Wikidata QID: Q126837565
cites work: Q4091421
cites work: Dominating Sets in Chordal Graphs
cites work: Semitotal domination in graphs
cites work: Q4368728
cites work: Q4368729
cites work: Perfect graphs involving semitotal and semipaired domination
cites work: Edge weighting functions on semitotal dominating sets
cites work: On matching and semitotal domination in graphs
cites work: Vertices contained in all or in no minimum semitotal dominating set of a tree
cites work: Semitotal domination in claw-free cubic graphs
cites work: Q4566369
cites work: Algorithmic aspects of semitotal domination in graphs
cites work: Total Domination in Graphs
cites work: Complexity and approximation ratio of semitotal domination in graphs
cites work: Semitotal domination in trees
DOI: 10.7151/DMGT.2254
published in: Discussiones Mathematicae Graph Theory
description: scientific article; zbMATH DE number 7451250