DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(2) (2013) 337-346
DOI: https://doi.org/10.7151/dmgt.1669

Strong equality between the Roman domination and independent Roman domination numbers in trees

Mustapha Chellali

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

Nader Jafari Rad

Department of Mathematics, Shahrood University of Technology
Shahrood, Iran
and
School of Mathematics
Institute for Research in Fundamental Sciences (IPM),
P.O. Box 19395-5746, Tehran, Iran

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)) = ∑u ∈ V(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).

Keywords: Roman domination, independent Roman domination, strong equality, trees

2010 Mathematics Subject Classification: 05C69.

References

[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.
[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.
[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.
[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:3<199::AID-NET4>3.0.CO;2-F .
[5]M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002) 325--334, doi: 10.7151/dmgt.1178.
[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.
[7]N. Jafari Rad and L. Volkmann, Changing and unchanging the Roman domination number of a graph, Util. Math. 89 (2012) 79--95.

Received 8 December 2010
Revised 24 November 2011
Accepted 5 April 2012

Close