The semitotal domination problem in block graphs (Q2062683)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The semitotal domination problem in block graphs |
scientific article |
Statements
The semitotal domination problem in block graphs (English)
0 references
3 January 2022
0 references
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
0 references
domination
0 references
semitotal domination
0 references
block graphs
0 references
undirected path graphs
0 references
NP-completeness
0 references