## 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 γ _{R} ^{p}(G), is the minimum weight of a perfect Roman dominating function in G. We show that if G is a cubic graph on n vertices, then γ^{R} _{p} (G) ≤ 3/4n, and this bound is best possible. Further, we show that if G is a k-regular graph on n vertices with k at least 4, then γ ^{R}_{p}(G) ≤ (k^{2}+k+3/k^{2}+3k+1) n.

Original language | English |
---|---|

Pages (from-to) | 143-152 |

Number of pages | 10 |

Journal | Applicable Analysis and Discrete Mathematics |

Volume | 12 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Apr 2018 |

## Keywords

- Dominating set
- Perfect dominating set
- Roman dominating function

## ASJC Scopus subject areas

- Analysis
- Discrete Mathematics and Combinatorics
- Applied Mathematics