Skip to main content
Article
Extremal Problems for Roman Domination
Faculty Publications & Research
  • E. W. Chambers
  • W. Kinnersley
  • N. Prince, Illinois Mathematics and Science Academy
  • D. B. West
Document Type
Article
Publication Date
1-1-2009
Abstract

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γR(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γR(G) + γR() and γR(G)γR(), improving known results for domination number. We prove that γR(G) ≤ 8n/11 when ᵟ(G) ≥ 2 and n ≥ 9, and this is sharp.

Comments

At the time of publication, Noah Prince was affiliated with the University of Illinois at Urbana-Champaign.

Citation Information
Chambers, E.W., Kinnersley, W., Prince, N., & West, D.B. (2009). Extremal problems for Roman domination. SIAM Journal on Discrete Mathematics, 23(3), 1575-1586.