Research Specifications

Home \Global Roman Domination in ...
Title
Global Roman Domination in Trees
Type of Research Article
Keywords
Roman dominating function · Roman domination number · Global Roman dominating function · Global Roman domination number
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.
Researchers maryam atapour (First Researcher)، Seyed Mahmoud Sheikholeslami Kavkani (Second Researcher)، Lutz Volkmann (Third Researcher)