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

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Eternal distance-2 domination in trees

Alexander Clow, Christopher van Bommel
Ars Combinatoria
Advanced Graph Theory Research
article

Eternal distance-2 domination in trees

Alexander Clow, Christopher van Bommel
article en

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 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.

Ars CombinatoriaVol. 163
Natural Sciences and Engineering Research Council of Canada
Openalex Percentile: Top 83%
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.