A note on the independent Roman domination in unicyclic graphs

• Autorzy: Chellali M. , Rad N. J.
• Języki publikacji: EN

Abstrakty

EN

A Roman dominating function (RDF) on a graph G= (V, E) is a function ƒ : V → {0, 1, 2} satisfying the condition that every vertex u for which ƒ(u) = 0 is adjacent to at least one vertex v for which ƒ(v)=2. The weight of an RDF is the value [formula]. An RDF ƒ 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 ΥR(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 note we characterize all unicyclic graphs G with ΥR(G) ≡ iR(G).

Słowa kluczowe

EN

Roman domination; independent Roman domination; strong equality

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2012
• Tom: Vol. 32, no. 4
• Strony: 715--718
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Chellali M.

autor

Rad N. J.

• University of Blida LAMDA-RO Laboratory, Department of Mathematics B.P. 270, Blida, Algeria,

Bibliografia

• [1] M. Adabi, E. Ebrahimi Targhi, N. Jafari Rad, M. Saied Moradi, Properties of independent Roman domination in graphs, Australasian Journal of Combinatorics 52 (2012), 11–18.
• [2] M. Chellali, N. Jafari Rad, Strong equality between the Roman domination and independent Roman domination numbers in trees, Discussiones Mathematicae Graph Theory, to appear.
• [3] E.J. Cockayne, P.M. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Mathematics 278 (2004), 11–22.
• [4] T.W. Haynes, M.A. Henning, P.J. Slater, Strong equality of domination parameters in trees, Discrete Mathematics 260 (2003), 77–87.
• [5] T.W. Haynes, M.A. Henning P.J. Slater, Strong equality of upper domination and independence in trees, Utilitas Math. 59 (2001), 111–124.
• [6] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199–206.
• [7] M.A. Henning, A characterization of Roman trees, Discussiones Mathematicae Graph Theory 22 (2002), 325–334.