Upper bounds on Roman domination numbers of graphs Academic Article uri icon

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.

published proceedings

  • Discrete Mathematics

author list (cited authors)

  • Liu, C., & Chang, G. J.

citation count

  • 29

complete list of authors

  • Liu, Chun-Hung||Chang, Gerard Jennhwa

publication date

  • January 2012