Upper bounds on Roman domination numbers of graphs

Chun Hung Liu, Gerard Jennhwa Chang

Research output: Contribution to journalArticlepeer-review

33 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

Keywords

  • Cocomparability graph
  • Domination
  • Forbidden subgraph
  • Minimum degree
  • Roman domination

Fingerprint

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

Cite this