Eternal Distance-2 Domination in Trees
Preprint
Abstract
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 characterise when trees have an eternal distance-2 domination number equal to their domination number or their distance-2 domination number, along with characterizing which trees 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, as well as constructing an infinite family of trees which meet said upper bound and another which meets the given lower bound.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Eternal Distance-k Domination on GraphsLa Matematica, 2023
- A method for eternally dominating strong gridsDiscrete Mathematics & Theoretical Computer Science, 2020
- Eternally dominating large gridsTheoretical Computer Science, 2019
- A note on the eternal dominating set problemInternational Journal of Game Theory, 2018
- Spy-game on graphs: Complexity and simple topologiesTheoretical Computer Science, 2018
- Protecting a graph with mobile guardsApplicable Analysis and Discrete Mathematics, 2016
- Graphs with equal domination and 2-distance domination numbersDiscussiones Mathematicae Graph Theory, 2011