Back to Search
Start Over
Complexity Issues on of Secondary Domination Number.
- Source :
- Algorithmica; Apr2024, Vol. 86 Issue 4, p1163-1172, 10p
- Publication Year :
- 2024
-
Abstract
- In this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding a minimum secondary dominating set in trees is presented. [ABSTRACT FROM AUTHOR]
- Subjects :
- COMPUTATIONAL complexity
DOMINATING set
TRIANGLES
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 86
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 176340004
- Full Text :
- https://doi.org/10.1007/s00453-023-01192-2