Perfect Roman domination in trees

Michael A. Henning, William F. Klostermeyer, Gary MacGillivray

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)


A perfect Roman dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u with f(u)=0 is adjacent to exactly one vertex v for which f(v)=2. The weight of a perfect Roman dominating function f is the sum of the weights of the vertices. The perfect Roman domination number of G, denoted γRp(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a tree on n≥3 vertices, then γRp(G)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.

Original languageEnglish
Pages (from-to)235-245
Number of pages11
JournalDiscrete Applied Mathematics
Publication statusPublished - 19 Feb 2018


  • Dominating set
  • Perfect dominating set
  • Roman dominating function
  • Tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Perfect Roman domination in trees'. Together they form a unique fingerprint.

Cite this