Eternal dominating set¶

A set of graph vertices occupied by mobile guards that can respond to every infinite sequence of vertex attacks while remaining a dominating set after each move.

Version: v2 · 2026-09-19 · History
Domain-specific #: 4427
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theoretic Security Games → Mathematics

Core Idea¶

Eternal domination minimizes guards under a declared movement and attack model, with one-guard, all-guards, multiple-occupancy, and eviction variants producing different invariants. An adversary selects an attacked vertex, legal guards move along edges, one occupies the target when required, and the post-move configuration must dominate every vertex for the next attack. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Forever Guard Game

Picture a town of houses joined by paths, with a few guards standing at some houses. A sneaky troublemaker picks a house, and a guard must walk along a path to it. After moving, the guards must still be close enough to protect every house for the next attack, again and again forever. The puzzle is finding the fewest guards that can always do this.

The Never-Ending Guard Game

Imagine a network of dots connected by lines, like towns joined by roads, with guards standing on some dots. An attacker picks a dot to attack, and guards move along the lines so that one of them ends up on that dot. After the move, every dot must either have a guard or be right next to one, so the guards are ready for the next attack. This has to work no matter how many attacks come. An eternal dominating set asks for the fewest guards that can always do this, and the answer depends on the rules, like whether one guard or all guards may move each turn.

Infinite-Attack Graph Domination

In graph theory, a dominating set is a set of vertices such that every vertex is in the set or adjacent to it. Eternal domination turns this into a never-ending game. An adversary attacks a vertex, guards move along edges, one guard must occupy the attacked vertex when the rules require it, and the new guard positions must again form a dominating set. The aim is the minimum number of guards that can respond forever, which is harder than ordinary domination because the defense must survive every possible sequence of attacks. Rule variants matter: one guard moving per turn, all guards moving, allowing several guards on one vertex, or 'eviction' versions each give different minimum numbers. So the movement and attack rules must be stated exactly.

An eternal dominating set arises from a two-player game on a graph. Guards start on an initial vertex set; an adversary repeatedly selects an attacked vertex, and the defender responds by moving guards along edges, occupying the target when the model requires. The configuration after every response must again be a dominating set, so the defense can continue indefinitely against any attack sequence. The objective is to minimize the number of guards. Variants matter: the one-guard model (only one guard moves per turn), the all-guards model, models allowing multiple occupancy of a vertex, and eviction variants each define different parameters. A precise statement must specify the graph, the initial guard set, attack visibility and legality, the movement model, occupancy rules, the response rule, domination after every turn, adversary power, and the minimization objective. Changing any of these can change the resulting invariant.

Scope of Application¶

Eternal dominating set belongs to graph theoretic security games and is useful where the analyst can specify the typed graph theoretic security games carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective are explicit. The scope is broad within that domain but bounded by the need for graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective are explicit. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Eternal dominating set can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Eternal dominating set. Eternal dominating set compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed graph theoretic security games carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theoretic security games because they reuse the typed graph theoretic security games carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, An adversary selects an attacked vertex, legal guards move along edges, one occupies the target when required, and the post-move configuration must dominate every vertex for the next attack., and type the carrier, state every parameter and convention in the definition, test that graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Eternal dominating set Domain-specific

Parents (1) — outgoing typed relations

Eternal dominating set is a kind of Coverage / Reachability Prime

It remains its own entry because its identity is fixed by graph, initial guard set, attack visibility and legality, movement model, occupancy, response rule, domination after every turn, adversary power, and minimum objective.

Hierarchy paths (2) — routes to 2 parentless roots

Eternal dominating set → is a kind of Coverage / Reachability → is a kind of Completeness

Show alternative path (1)

Neighborhood in Abstraction Space¶

Eternal dominating set sits in a crowded region of the domain-specific corpus (15^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Pursuit Games on Graphs (5 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25