Article ID Journal Published Year Pages File Type
6871554 Discrete Applied Mathematics 2018 11 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,