Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees

Mustapha Chellali; Nader Jafari Rad

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 2, page 337-346
  • ISSN: 2083-5892

Abstract

top
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 is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).

How to cite

top

Mustapha Chellali, and Nader Jafari Rad. "Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees." Discussiones Mathematicae Graph Theory 33.2 (2013): 337-346. <http://eudml.org/doc/268140>.

@article{MustaphaChellali2013,
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 is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).},
author = {Mustapha Chellali, Nader Jafari Rad},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Roman domination; independent Roman domination; strong equality; trees},
language = {eng},
number = {2},
pages = {337-346},
title = {Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees},
url = {http://eudml.org/doc/268140},
volume = {33},
year = {2013},
}

TY - JOUR
AU - Mustapha Chellali
AU - Nader Jafari Rad
TI - Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 2
SP - 337
EP - 346
AB - 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 is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).
LA - eng
KW - Roman domination; independent Roman domination; strong equality; trees
UR - http://eudml.org/doc/268140
ER -

References

top
  1. [1] E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22. doi:10.1016/j.disc.2003.06.004[Crossref] Zbl1036.05034
  2. [2] T.W. Haynes, M.A. Henning and P.J. Slater, Strong equality of domination parameters in trees, Discrete Math. 260 (2003) 77-87. doi:10.1016/S0012-365X(02)00451-X[Crossref] Zbl1020.05051
  3. [3] T.W. Haynes, M.A. Henning and P.J. Slater, Strong equality of upper domination and independence in trees, Util. Math. 59 (2001) 111-124. Zbl0980.05038
  4. [4] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206. doi:10.1002/(SICI)1097-0037(199810)32:3h199::AID-NET4i3.0.CO;2-F[Crossref] Zbl0997.05074
  5. [5] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 325-334. doi:10.7151/dmgt.1178[Crossref] 
  6. [6] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003) 101-115. doi:10.1016/S0012-365X(03)00040-2[Crossref] 
  7. [7] N. Jafari Rad and L. Volkmann, Changing and unchanging the Roman domination number of a graph, Util. Math. 89 (2012) 79-95. Zbl1273.05162

NotesEmbed ?

top

You must be logged in to post comments.