Upper bounds on Roman domination numbers of graphs
Journal
Discrete Mathematics
Journal Volume
312
Journal Issue
7
Pages
1386-1391
Date Issued
2012
Author(s)
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)=∑ v∈V(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.
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)=∑ v∈V(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.
SDGs
Type
journal article