A Characterization of Trees with Large Roman Domination Number

Subject Areas : Statistics

حسین . Abdollahzadeh Ahangar ¹ , مهلا . Khaibari ² , N. Jafari Rad ³

1 - Department of Basic Science Babol Noshirvani University of Technology, Babol, Iran
2 - Department of Basic Science Babol Noshirvani University of Technology, Babol, Iran
3 - Department of Mathematics Shahrood University of Technology, Shahrood, Iran

Received: 2016-08-12 Accepted : 2016-09-17 Published : 2016-06-21

Keywords: تابع احاطه گر رومی, عدد احاطه گر رومی,

Abstract :

A Roman dominating function (RDF) on a graph G = 􀵫V،E􀵯 is a function f: V(G) → {0،1،2}satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least onevertex v for which f(v) = 2. The weight of an RDF f is w(f) = Σ􀭴∈􀭚 f(v). The Romandomination number of G is the minimum weight of an RDF in G. In this paper, wecharacterize all trees T of order n whose Roman domination number is n − 3.