|
Abstract
|
A function f : V(G) → {0, 1, 2} on graph G = (V(G), E(G)) satisfying
the condition that every vertex u for which f (u) = 0 is adjacent at least one vertex v
for which f (v) = 2 is a Roman dominating function (RDF). The weight of an RDF is
the sum of its function value over all vertices. The Roman domination number of G,
denoted by γR(G), is the minimum weight of an RDF on G. An RDF f : V(G) →
{0, 1, 2} is called a global Roman dominating function (GRDF) if f is also an RDF
of the complement G of G. The global Roman domination number of G, denoted by
γgR(G), is the minimum weight of a GRDF on G. In this paper, we initiate global
Roman domination number and study the basic properties of global Roman domination
of a graph. Then we present some sharp bounds for global Roman domination number.
In particular, we prove that for any tree of order n ≥ 4, γgR(T ) ≤ γR(T ) + 2 and we
characterize all trees with γgR(T ) = γR(T ) + 2 and γgR(T ) = γR(T ) + 1.
|