Roman Dominating Set¶

A graph labeling assigns each vertex 0, 1, or 2 so every zero vertex neighbors a two vertex; the least total label weight is its Roman domination number.

Version: v1 · 2026-10-07 · History
Domain-specific #: 14005
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Graph Domination, Graph Labeling → Mathematics
Aliases: Roman Dominating Function

Core Idea¶

A Roman dominating set assigns each vertex of a graph 0, 1, or 2. Every zero-labeled vertex must have an adjacent vertex labeled two. The original authors represent the positive labels as a multiset: a vertex labeled two appears twice, while a one-labeled vertex appears once. Its weight is the sum of labels. The Roman domination number \(\gamma_R(G)\) is the least weight of any feasible labeling; a feasible set does not have to attain that minimum.[^ref-f0217e6142c9]

Constitutive roles. A graph supplies vertices and adjacency; a total function maps vertices to 0/½; the local condition tests every zero; and the sum counts units with multiplicity. The motivating defense story explains why one two-labeled site can protect an adjacent zero while retaining a unit, but graph membership is decided by the exact labeling rule.[^{ref-f0217e6142c9][}ref-98955786a7cf]

Scope of Application¶

The definition applies to any specified graph. On a path, a two can protect adjacent sites along a chain; on a Cartesian ladder, a middle-column two can cover corners in its row. Cockayne and colleagues prove exact minima for paths and 2×\(n\) grids. Yero and Rodríguez-Velázquez apply the same Roman function to Cartesian and strong product graphs, whose adjacency changes the feasible placements. These are literal graph cases; a real service allocation needs an explicit graph and validated assumptions before it can be called Roman domination.[^{ref-f0217e6142c9][}ref-98955786a7cf]

Clarity¶

Test feasibility by checking that every zero has a neighboring two. Then sum the labels to find the weight. To claim the minimum, also show that no lighter feasible assignment exists. An all-ones labeling is valid because it has no zeros, even when a lower-weight Roman labeling exists. Saving only the set of occupied vertices loses the distinction between one and two and cannot reconstruct the weight or the rule's protection capacity.[^ref-f0217e6142c9]

Manages Complexity¶

A graph, ternary map, local test, and additive weight replace a story about possible stationings with a verifiable mathematical object. One valid labeling certifies an upper bound on \(\gamma_R\), but a separate lower bound or proved family formula establishes optimality. On P4, \((1,0,2,0)\) has weight three; the path proposition shows three is minimum. On the 2×3 ladder, two middle-column twos protect four zero corners at weight four; the grid proposition shows four is minimum.[^ref-f0217e6142c9]

Abstract Reasoning¶

For a new graph, list its edges and try 0/½ assignments. Reject each one with a zero lacking a two-neighbor, then compare the weights of the survivors. Ask whether paying two at one site permits enough nearby sites to become zero to lower total cost. The answer depends on adjacency: a path's endpoints and a ladder's cycles produce different useful placements. The ordinary domination number gives a broad comparison, \(\gamma(G)\le\gamma_R(G)\le2\gamma(G)\), but does not replace an exact proof.[^{ref-f0217e6142c9][}ref-98955786a7cf]

Knowledge Transfer¶

The same labeling and test transfer literally between paths, grids, and graph products. Their optimal values and preferred placements do not transfer automatically because the edges change. More broadly, Function Mapping and Constraint are the strict constituent parents: the first supplies the vertex assignment, and the second the required zero-to-two predicate. Their generic patterns can appear elsewhere, but the Roman identity requires this graph-specific rule.[^{ref-f0217e6142c9][}ref-98955786a7cf]

Example¶

Four-vertex path P4. Mapped back: carrier = four vertices in chain order; assignment = \((1,0,2,0)\); feasibility = both zeros neighbor vertex 3, labeled two; weight = three; minimum = Cockayne and colleagues' Proposition 5(b) gives \(\gamma_R(P4)=3\). The displayed labeling is a witness, while the proposition supplies optimality.[^ref-f0217e6142c9]

2×3 Cartesian ladder. Mapped back: carrier = two rows by three columns with horizontal and vertical edges; assignment = two middle-column twos and four corner zeros; feasibility = each zero corner adjoins a middle two in its row; weight = four; minimum = the grid result in Proposition 8 gives \(\gamma_R(G_{2,3})=4\). Its cycles and degree-three middle sites differ from the path, but the Roman predicate is unchanged.[^{ref-f0217e6142c9][}ref-98955786a7cf]

Relationships to Other Abstractions¶

Current abstraction Roman Dominating Set Domain-specific

Parents (2) — more general patterns this builds on

Roman Dominating Set is part of Constraint Prime

A required local predicate permits a zero label only beside a two-labeled neighbor.
Roman Dominating Set is part of Function (Mapping) Prime

A Roman dominating set requires a total graph-vertex-to-0/½ assignment to state its multiplicities and weight.

Hierarchy paths (2) — routes to 2 parentless roots

Roman Dominating Set → Constraint

Show alternative path (1)

Neighborhood in Abstraction Space¶

Roman Dominating Set sits in a moderately populated region (58^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Classes & Invariants (37 abstractions)

Nearest neighbors

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

Not to Be Confused With¶

Ordinary dominating set: a selected-vertex set lacks the Roman one-versus-two multiplicity and its special zero-neighbor condition.[^ref-f0217e6142c9]
Roman domination number: the minimum weight is a graph invariant; a particular feasible Roman multiset may weigh more.[^ref-f0217e6142c9]
Two one-neighbors: their combined labels do not substitute for a single adjacent two under the base rule.[^ref-f0217e6142c9]
Graph coloring: adjacent Roman vertices need not receive different labels.[^ref-f0217e6142c9]
Literal troop or emergency deployment: the mathematical model establishes no real-world response capability without independently stated assumptions.[^ref-f0217e6142c9]

References¶

[^ref-f0217e6142c9]: Ernie J. Cockayne, Paul A. Dreyer Jr., Sandra M. Hedetniemi, and Stephen T. Hedetniemi, “Roman Domination in Graphs”, Discrete Mathematics 278 (2004), 11–22, doi:10.1016/j.disc.2003.06.004. Full original manuscript uploaded by coauthor Dreyer inspected and publisher bibliographic record checked. Manuscript §§1–2 define the function, Roman multiset/set convention, weight, minimum, and ordinary-domination bound; manuscript §3 Proposition 5 gives path and cycle minima and Proposition 8 gives the 2×\(n\) grid minimum. The displayed P4 and ladder labelings are direct checked witnesses, not quoted figures.

[^ref-98955786a7cf]: Ismael G. Yero and Juan A. Rodríguez-Velázquez, “Roman Domination in Cartesian Product Graphs and Strong Product Graphs”, original author manuscript (2011), arXiv:1111.3517. Full 13-page manuscript inspected. Abstract and §1 restate Roman function and weight; §§1–2 define Cartesian-product adjacency and study bounds; Theorem 10 gives a factor-label construction on Cartesian products. The P4 and 2×3 exact minima cited here come from Cockayne et al., not from this later paper.