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 is a constrained way to place zero, one, or two units at the vertices of a graph. Formally, a function \(f:V(G)\to\{0,1,2\}\) is Roman dominating when every vertex assigned zero has an adjacent vertex assigned two. A site with one unit is occupied itself; a two-unit neighbor has a reserve that can protect a zero site while retaining one at home in the motivating defense story. The graph rule is static: it asks whether the labeling meets the local adjacency condition, not whether actual troops or response vehicles have moved.^[1]^[2]

The original authors call the positive-label object a multiset: a vertex labeled two occurs twice, while a vertex labeled one occurs once. They shorten this to “set” with that multiplicity understood. The total weight is \(w(f)=\sum_{v\in V(G)}f(v)\). The Roman domination number, \(\gamma_R(G)\), is the minimum such weight among feasible functions. A feasible labeling need not be minimum; the multiset, its weight, and the minimum graph invariant are related but distinct objects.^[1]

Structural Signature¶

Graph carrier and adjacency. Vertices are the sites, and edges determine one-step protection. Changing the edges can alter which zero sites are feasible and the least weight.^[1]^[2]
Ternary vertex assignment. Each vertex receives exactly one of 0, 1, or 2. The function retains the multiplicity that an ordinary subset of occupied vertices loses.^[1]
Zero-to-two feasibility condition. Every zero vertex needs at least one immediately adjacent two vertex. Two separate one-labeled neighbors do not replace one two-labeled neighbor under this rule.^[1]
Weight. Summing all labels counts a one site once and a two site twice. Weight compares feasible defenses; it is not the same as the cardinality of positive-labeled vertices.^[1]
Minimum over feasible assignments. \(\gamma_R(G)\) chooses the least feasible weight. A nonminimum Roman dominating set remains Roman dominating even though it does not attain this number.^[1]
Certificate and proof. A concrete valid labeling certifies an upper bound on \(\gamma_R\). Establishing the minimum also needs a lower-bound argument or a proved family result; a witness alone cannot exclude lighter assignments.^[1]

What It Is Not¶

It is not an ordinary dominating set with a martial name. A usual dominating set records whether a vertex is selected, while the Roman rule distinguishes one from two at selected vertices and places a specific obligation on every zero. If only the positive-label subset is saved, the number of units and even the feasibility of the zero sites can no longer be reconstructed. The authors' “set” terminology explicitly preserves multiplicity.^[1]

It is also not a demand that every valid labeling be optimal. On the four-vertex path, labeling every vertex one is feasible because no vertex has label zero; its weight is four. The Roman domination number is three. Treating the all-ones assignment as invalid would confuse the feasibility predicate with the separate minimum-weight problem.^[1]

Nor does the definition license a literal claim about ancient history or modern emergency deployment. The legion story explains why a reserve of two is different from one; mathematical membership is decided by the graph, labeling, and rule. A service system could instantiate the model only after its sites, links, units, and response assumptions were actually specified.^[1]

Scope of Application¶

The rule is defined for graphs whose vertices and adjacency are stated. On a path, endpoints have only one neighbor and a two label can protect at most its adjacent zero sites. On a 2×3 Cartesian ladder, there are two rows, three columns, and horizontal and vertical edges; the middle-column sites can each cover the corners in their row. Cockayne and colleagues prove separate exact minima for paths and 2×\(n\) grids, so these are distinct literal graph realizations of one labeling identity rather than two resource stories with changed nouns.^[1]

Yero and Rodríguez-Velázquez study the same Roman function on Cartesian and strong product graphs. Their product definitions change how graph adjacency is formed, then ask how Roman domination of the resulting graph relates to its factors. This extends the literal mathematical habitat without changing the base zero-to-two predicate. The Roman domination number satisfies \(\gamma(G)\le\gamma_R(G)\le 2\gamma(G)\), where \(\gamma(G)\) is the ordinary domination number; the inequality helps compare parameters but does not define Roman feasibility.^[1]^[2]

Clarity¶

The useful distinction is feasible labeling versus least-cost labeling. To test the first, inspect every zero site and find a neighboring two. To establish the second, add the labels and show that no feasible assignment weighs less. This separates three claims often blurred in prose: “this placement works,” “it costs three,” and “three is the minimum.” A valid labeling proves the first two, while a lower-bound result is needed for the third.^[1]

A second distinction is multiplicity versus occupancy. A path assignment \((1,0,2,0)\) occupies vertices 1 and 3, but the ordinary set \(\{1,3\}\) hides the fact that vertex 3 carries two and protects zeros at vertices 2 and 4. The Roman multiset or the full function retains that fact. The graph alone cannot tell which occupied site holds the reserve.^[1]

Manages Complexity¶

The abstraction compresses many possible stationings into a small formal specification: a graph, a ternary map, one local feasibility test, and an additive weight. For a proposed assignment, verification requires checking zero vertices against adjacent twos and summing labels, rather than narrating every possible move. Optimization then searches among exactly those feasible maps. Different graph families change the search space and attainable minimum without changing the rule.^[1]^[2]

The distinction between a witness and a bound prevents overclaiming. On P4, the assignment \((1,0,2,0)\) gives weight three, so \(\gamma_R(P4)\le3\). Cockayne and colleagues' path proposition gives \(\gamma_R(P4)=3\), supplying the matching lower bound. On the 2×3 ladder, two middle-column twos give weight four, and their grid proposition proves that four is optimal. The same compression works for both, but the placement logic depends on topology.^[1]

Abstract Reasoning¶

Given a new graph, first name its vertices and edges. Assign 0, 1, or 2 to each vertex, then reject any assignment with a zero that lacks a two-labeled neighbor. Add the remaining labels to get the weight. A promising construction gives an upper bound on the optimum; to claim the Roman domination number, derive or cite a lower bound that rules out every lighter feasible construction. Do not treat the number of occupied sites as the cost, because a two-labeled site costs two.^[1]

A useful search move is to ask whether paying two at one vertex permits enough neighboring vertices to become zero to reduce total weight. That calculation must be repeated when adjacency changes. The four-vertex path has terminal sites; the ladder has cycles and two degree-three middle sites. Their optimal assignments share the rule but need different placements. The inequality against ordinary domination gives a broad check on a proposed answer without replacing exact proof.^[1]^[2]

Knowledge Transfer¶

Within graph theory, the same function-and-constraint test transfers from a path to a Cartesian grid or another graph family. What transfers literally is the ternary assignment, zero-to-two adjacency predicate, and weight definition. What does not transfer automatically is the optimum formula or a favored site placement: new edges change how many zero sites one two site can cover. Product-graph results give bounds and constructions for those different carriers rather than erasing the factor graphs' details.^[1]^[2]

Beyond graph stationing, Function Mapping and Constraint are the portable constituents: assigning values to objects and accepting only assignments that satisfy a predicate occurs widely. The Roman name does not travel literally to every constrained allocation. Unless the receiving system has vertices, adjacency, exactly the 0/½ distinction, and the adjacent-two condition, it is an analogy to the defense story rather than this named graph object.^[1]

Examples¶

Four-vertex path P4. Label the vertices in chain order \((1,0,2,0)\). Mapped back: carrier = four vertices with consecutive edges; assignment = one, zero, two, zero; feasibility = both zero vertices neighbor vertex 3 labeled two; weight = three; minimum = Cockayne and colleagues' Proposition 5(b) gives \(\gamma_R(P4)=3\). The displayed labels are a directly checked witness; the published family proposition establishes optimality.^[1]

2×3 Cartesian ladder. Label the two middle-column vertices two and all four corners zero. Mapped back: carrier = two rows by three columns with horizontal and vertical edges; assignment = two middle twos and four corner zeros; feasibility = each corner adjoins the middle site of its row; weight = four; minimum = Proposition 8 gives \(\gamma_R(G_{2,3})=4\). This grid has cycles and degree-three middle vertices, unlike the terminal path, while preserving the same Roman predicate.^[1]^[2]

Structural Tensions¶

Cost of a two-unit site versus coverage it permits. A two costs more than a one at its own vertex, yet can make neighboring zeros legal. Reducing the number of twos can force more ones or twos elsewhere; adding a two where few zeros can be released wastes weight. The minimum depends on the graph's adjacency, so neither “always choose two” nor “avoid two” solves the problem. Diagnostic: which site, if given two units, would let enough neighbors receive zero to lower the total? On P4 one two at vertex 3 suffices alongside one one; on the ladder two middle-column twos protect four zeros.^[1]

Structural–Framed Character¶

Roman domination sits near the structural end of the structural–framed spectrum: the map, adjacency rule, and minimum can be checked mathematically on a specified graph. Evaluative weight enters in choosing to minimize total units; the feasibility condition itself is exact once the model is fixed. Human-practice dependence enters when someone chooses what a vertex, edge, or unit represents, and whether the static model fits a real task. Institutional origin in a historical story or graph-theory paper is not a membership condition.^[1]

Vocabulary travel is literal among different graph families when the same ternary rule is retained; it is figurative when the story of defending an unstaffed site is applied without that graph rule. Import versus recognition: one recognizes a Roman dominating set by reconstructing its multiset/function and checking every zero-to-two edge, rather than importing “Roman” from an analogy or a paper title. Its character: a strongly structural, graph-specific labeling whose cost interpretation can guide resource models only when their assumptions are explicitly mapped.^[1]^[2]

Structural Core vs. Domain Accent¶

The structural core is a vertex-to-label map plus a necessary local constraint: zeros require neighboring twos. Function Mapping and Constraint supply those portable pieces. The labels exactly 0/½, graph adjacency, reserve interpretation, multiset multiplicity, and minimization over feasible labelings are the domain-bound Roman mechanism. Paths, grids, and product graphs change the carrier topology; the legion story and any prospective application are contextual accents.^[1]^[2]

The named entry does not clear the Prime bar. If graph adjacency and the adjacent-two rule are removed, what remains is generic mapping, constraint, and perhaps an optimization problem. Those broader patterns travel; the Roman dominating set itself does not. The associated \(\gamma_R(G)\) is a graph invariant, but a particular feasible multiset is not, so Graph Invariant is related rather than an exceptionless parent of the whole entry.^[1]

This entry is part of Constraint and is part of Function (Mapping).

The strict child-to-Function Mapping edge is composition/part of, parent in child. Every Roman set needs a total function from vertices to 0/½; removing it loses the multiplicities and the zero class. The strict child-to-Constraint edge has the same direction: the adjacency-to-two predicate is the rule that separates feasible from infeasible ternary mappings. Neither parent alone specifies this particular graph labeling.^[1]

Optimization describes the associated search for a least-weight feasible function, and Graph Invariant describes the resulting \(\gamma_R\) assignment to graphs. Both are related, but an arbitrary feasible Roman set need not be minimum or itself a graph invariant. Graph Coloring's live signature requires different labels at adjacent conflict vertices, which the Roman rule does not; equal labels on adjacent vertices are allowed. Connected and eternal domination add conditions absent here.^[1]^[2]

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: records selected vertices; the Roman representation retains one-versus-two multiplicity and its special zero-neighbor test.^[1]
Minimum Roman number: \(\gamma_R(G)\) is a minimum weight, while a Roman dominating multiset may have a larger weight.^[1]
Graph coloring: Roman labels are not colors required to differ across edges; the condition singles out zero vertices and adjacent twos.^[1]
Two one-neighbors as a substitute: a zero lacking a two-neighbor fails the base rule, regardless of the sum of its neighbors' labels.^[1]
Historical or emergency deployment: the graph model needs an explicit carrier and validated assumptions before it can be read as an actual allocation.^[1]

References¶

[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29 ↩30 ↩31 ↩32 ↩33 ↩34 ↩35

[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j