Perfect Roman domination in regular graphs

Michael A. Henning, William F. Klostermeyer

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

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 γ Rp(G) ≤ (k2+k+3/k2+3k+1) n.

Original languageEnglish
Pages (from-to)143-152
Number of pages10
JournalApplicable Analysis and Discrete Mathematics
Volume12
Issue number1
DOIs
Publication statusPublished - 1 Apr 2018

Keywords

  • Dominating set
  • Perfect dominating set
  • Roman dominating function

ASJC Scopus subject areas

  • Analysis
  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

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

Cite this