In graph theory, a Roman dominating set (RDS) is a special type of dominating set inspired by historical military defense strategies of the Roman Empire. The concept models a scenario where cities (vertices) can be defended by legions stationed either within the city or in neighboring cities. A city is considered secure if it either has at least one legion stationed there, or if it has no legions but is adjacent to a city that has at least two legions, allowing one legion to be sent for defense while leaving the original city still protected.
The Roman domination number of a graph measures the minimum total number of legions needed to protect all cities according to this strategy.
Let be a graph. A Roman dominating function (RDF) is a function such that for every vertex with , there exists a vertex adjacent to with .
The weight of a Roman dominating function is . The Roman domination number is the minimum weight among all Roman dominating functions for .
Equivalently, let be an ordered partition of where . Then is a Roman dominating function if and only if every vertex in is adjacent to at least one vertex in .
For the complete graph with , , achieved by assigning 2 to any single vertex and 0 to all others.
For the path graph and cycle graph , .
For the empty graph , , since each vertex must be assigned at least 1.
For the complete -partite graph with partition sizes :
Several properties of Roman domination were established by Cockayne et al.:
A graph is called a Roman graph if . This occurs if and only if has a Roman dominating function of minimum weight with .
The Roman domination value of a vertex extends the concept of Roman domination by considering how many minimum Roman dominating functions assign positive values to that vertex.
For a graph , let be the set of all -functions (Roman dominating functions of minimum weight). For a vertex , the Roman domination value is defined as:
Some basic properties of Roman domination value are known:
Several extremal results have been established for Roman domination numbers.
For any connected -vertex graph with , . Equality holds if and only if is or obtained from copies of by adding a connected subgraph on the set of centers.
For any -vertex graph with , .
For any -vertex graph with , .
If is a connected -vertex graph with and , then .
The decision problem for Roman domination is NP-complete, even when restricted to bipartite, chordal, or planar graphs. However, polynomial-time algorithms exist for computing the Roman domination number on interval graphs, cographs, and strongly chordal graphs.