Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871554 | Discrete Applied Mathematics | 2018 | 11 Pages |
Abstract
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)â¤45n, and we characterize the trees achieving equality in this bound.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael A. Henning, William F. Klostermeyer, Gary MacGillivray,