Malaysian Journal of Mathematical Sciences, January 2017, Vol. 11, No. 1
Graphs with Large Roman Domination Number
Ahangar, H. A. and Khaibari, M.
Corresponding Email: ha.ahangar@nit.ac.ir
Received date: 22 September 2016
Accepted date: 31 December 2016
Abstract:
A Roman dominating function (RDF) on a graph \(G = (V, E)\) is a function \(f:V(G)\rightarrow \left \{ 0,1,2 \right \}\) satisfying the condition that every vertex with label 0 is adjacent to a vertex with label 2. The weight of an RDF \(f\) is \(w(f)=\sum_{\upsilon\in V}f(\upsilon)\). The Roman domination number of \(G\) is the minimum weight of an RDF in \(G\). In this article, we characterize all connected graphs \(G\) of order \(n\) whose Roman domination number is \(n-1\) or \(n-2\).
Keywords: Roman dominating function, Roman domination number
Indexing
