Roman dominating set


In graph theory, a Roman dominating set is a special type of dominating set inspired by historical military defense strategies of the Roman Empire. The concept models a scenario where cities 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.

Definition

Let be a graph. A Roman dominating function 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.

Examples

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 :
  • if.
  • if.
  • if.

    Basic properties

Several properties of Roman domination were established by Cockayne et al.:
  • For any graph,, where is the domination number.
  • if and only if is the empty graph.
  • If has a vertex of degree, then.
  • For any Roman dominating function :
  • * The subgraph induced by has maximum degree at most 1.
  • * No edge joins and.
  • * Each vertex in is adjacent to at most two vertices in.
  • * is a dominating set for the subgraph induced by.
A graph is called a Roman graph if. This occurs if and only if has a Roman dominating function of minimum weight with.

Roman domination value

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. For a vertex, the Roman domination value is defined as:
Some basic properties of Roman domination value are known:
  • , where is the number of -functions
  • If there is a graph isomorphism mapping vertex in to vertex in, then

    Extremal problems

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.

Algorithms and complexity

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.