On the Roman domination number of a graph |
| |
Authors: | O Favaron H Karami SM Sheikholeslami |
| |
Institution: | a Univ Paris-Sud, LRI, UMR 8623, Orsay, F-91405, France b CNRS, Orsay, F-91405, France c Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, Islamic Republic of Iran |
| |
Abstract: | A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γR(G) of G is the minimum of ∑v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γR(G) is called a γR(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V0,V1,V2) of V, where Vi={v∈V∣f(v)=i}. Cockayne et al. E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V0|,|V1|,|V2| for a γR-function f=(V0,V1,V2) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γR-function f=(V0,V1,V2) of a connected graph G of order n≥3, , and . |
| |
Keywords: | Roman domination number |
本文献已被 ScienceDirect 等数据库收录! |
|