Search
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.
Citations
-
2
CrossRef
-
0
Web of Science
-
2
Scopus
Cite as
Full text
download paper
downloaded 74 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s00453-023-01192-2
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
ALGORITHMICA
ISSN: 0178-4617 - Language:
- English
- Publication year:
- 2023
- Bibliographic description:
- Raczek J.: Complexity Issues on of Secondary Domination Number// ALGORITHMICA -, (2023),
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s00453-023-01192-2
- Sources of funding:
-
- Free publication
- Verified by:
- Gdańsk University of Technology
seen 75 times
Recommended for you
On the connected and weakly convex domination numbers
- M. Lemańska,
- M. Dettlaff,
- D. Osula
- + 1 authors
2020
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
- S. Das,
- D. Dereniowski,
- C. Karousatou
2018