Upper bounds on Roman domination numbers of graphs

Chun-Hung Liu, Gerard Jennhwa Chang

Research output: Contribution to journalArticle

23 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1386-1391
Number of pages6
JournalDiscrete Mathematics
Volume312
Issue number7
DOIs
StatePublished - Apr 6 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Upper bounds on Roman domination numbers of graphs'. Together they form a unique fingerprint.

  • Cite this