Eternal distance-2 domination in trees
We consider the eternal distance-2 domination problem, recently proposed by Cox, Meger, and Messinger, on trees. We show that finding a minimum eternal distance-2 dominating set of a tree is linear time in the order of the graph by providing a fast algorithm. Additionally, we characterize trees that have eternal distance-2 domination number equal to their domination number or their distance-2 domination number, {along with trees that are} eternal distance-2 domination critical. We conclude by providing general upper and lower bounds for the eternal distance-k domination number of a graph. We construct an infinite family of trees which meet said upper bound and another infinite family of trees whose eternal distance-k domination number is within a factor of 2 of the given lower bound.
Authors
- Alexander Clow
- Christopher van Bommel
Publication Details
- Journal
- Ars Combinatoria
- Published
- 2025-06-27
- DOI
- https://doi.org/10.61091/ars163-03
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Natural Sciences and Engineering Research Council of Canada