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)≤[Formula presented]n, and we characterize the trees achieving equality in this bound.
Original language | English |
---|---|
Pages (from-to) | 235-245 |
Number of pages | 11 |
Journal | Discrete Applied Mathematics |
Volume | 236 |
DOIs | |
Publication status | Published - 19 Feb 2018 |
Keywords
- Dominating set
- Perfect dominating set
- Roman dominating function
- Tree
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics