An Upper Bound for the Eternal Roman Domination Number

Richard Brewster, Gary MacGillivray () and Ethan Williams
Additional contact information
Richard Brewster: Department of Mathematics and Statistics, Thompson Rivers University, Kamloops, BC V2C 0C8, Canada
Gary MacGillivray: Department of Mathematics and Statistics, University of Victoria, Victoria, BC V8W 2Y2, Canada
Ethan Williams: Institute of Discrete Mathematics, Graz University of Technology, 8010 Graz, Austria

Mathematics, 2025, vol. 13, issue 3, 1-13

Abstract: Imagine using mobile guards to defend the vertices of a graph G from a sequence of attacks subject to the conditions that after each attack: (i) each guard either remains in place or moves to an adjacent vertex; (ii) the configuration of guards forms a Roman-dominating set; and (iii) there is at least one guard on each attacked vertex. We show that it is always possible to defend the vertices of a tree with n vertices using at most 5 n 6 guards and that this bound is tight.

Keywords: domination; pursuit-evasion game; discrete-time graph process (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/3/437/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/3/437/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:3:p:437-:d:1578858

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().