Roman domination in graphs

https://doi.org/10.1016/j.disc.2003.06.004Get rights and content
Under an Elsevier user license
open archive

Abstract

A Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V)=∑uVf(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper, we study the graph theoretic properties of this variant of the domination number of a graph.

Keywords

Graph theory
Domination
Facilities location

Cited by (0)