Trees with strong equality between the Roman domination number and the unique response Roman domination number

Nader Jafari Rad, Chun Hung Liu

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = ∑ u∈V (G) f(u). A function f: V (G) → {0, 1, 2} with the ordered partition (V 0, V 1, V 2) of V (G), where V i = {υ ∈ V (G) {pipe} f(υ) = i} for i = 0, 1, 2, is a unique response Roman function if x ∈ V 0 implies {pipe}N(x) ∩ V 2{pipe} ≤ 1 and x ∈ V 1 ∪ V 2 implies that {pipe}N(x) ∩ V 2{pipe} = 0. A function f: V (G) → {0, 1, 2} is a unique response Roman dominating function (or just URRDF) if it is a unique response Roman function and a Roman dominating function. The Roman domination number γ R(G) (respectively, the unique response Roman domination number u R(G)) is the minimum weight of an RDF (respectively, URRDF) on G. We say that γ R(G) strongly equals u R(G), denoted by γ R(G) ≡ u R(G), if every RDF on G of minimum weight is a URRDF. In this paper we provide a constructive characterization of trees T with γ R(T) ≡ u R(T).

Original languageEnglish (US)
Pages (from-to)133-140
Number of pages8
JournalAustralasian Journal of Combinatorics
Volume54
Issue number2
StatePublished - Oct 4 2012

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Trees with strong equality between the Roman domination number and the unique response Roman domination number'. Together they form a unique fingerprint.

  • Cite this