Upper bounds on Roman domination numbers of graphs
Overview
Research
Identity
Additional Document Info
View All
Overview
abstract
A Roman dominating function of a graph G is a function fV(G)0,1,2 such that whenever f(v)=0 there exists a vertex u adjacent to v with f(u)=2. The weight of f is w(f)= vV(G) f(v). The Roman domination number R (G) of G is the minimum weight of a Roman dominating function of G. This paper establishes a sharp upper bound on the Roman domination numbers of graphs with minimum degree at least 3. An upper bound on the Roman domination numbers of connected, big-claw-free and big-net-free graphs is also given. 2012 Elsevier B.V. All rights reserved.