Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers

Document Type: Research Paper


1 Azarbaijan Shahid Madani University

2 University of Blida LAMDA-RO Laboratory


A $2$-\emph{rainbow dominating function} (2RDF) on a graph $G=(V,E)$ is a‎ ‎function $f$ from the vertex set $V$ to the set of all subsets of‎ ‎the set $\{1,2\}$ such that for any vertex $v\in V$ with‎ ‎$f(v)=\emptyset$ the condition $\bigcup_{u\in N(v)}f(u)=\{1,2\}$‎ ‎is fulfilled‎. ‎A 2RDF $f$ is independent (I2RDF) if no two vertices‎ ‎assigned nonempty sets are adjacent‎. ‎The weight of a 2RDF‎ ‎$f$ is the value $\omega(f)=\sum_{v\in V}|f (v)|$‎. ‎The‎ ‎2-\emph{rainbow domination number} $\gamma_{r2}(G)$ (respectively‎, ‎the independent $2$-rainbow domination number $i_{r2}(G)$‎) ‎is the minimum weight of a 2RDF (respectively‎, ‎I2RDF) on $G$‎. ‎We‎ say that $\gamma_{r2}(G)$ is strongly equal to $i_{r2}(G)$ and‎ ‎denote by $\gamma_{r2}(G)\equiv i_{r2}(G)$‎, ‎if every 2RDF on $G$‎ ‎of minimum weight is an I2RDF‎. ‎In this paper we‎ ‎characterize all unicyclic graphs $G$ with $\gamma_{r2}(G)\equiv i_{r2}(G)$‎.


Main Subjects

J. Amjadi, M. Falahat, N. Jafari Rad and S. M. Sheikholeslami Strong equality between the $2$-rainbow domination and independent $2$-rainbow domination numbers in trees. Bull. Malays. Math. Sci. Soc., (to appear).
B. Bresar, M. A. Henning and D. F. Rall (2008). Rainbow domination in graphs. Taiwanese J. Math.. 12, 213-225
B. Bresar and T. K. Sumenjak (2007). On the $2$-rainbow domination in graphs. Discrete Appl. Math.. 155, 2394-2400
M. Chellali and N. Jafari Rad Independent $2$-rainbow domination in graphs. J. Combin. Math. Combin. Comput., (to appear).
M. Chellali and N. Jafari Rad (2013). Strong equality between the Roman domination and independent Roman domination numbers in trees. Discuss. Math. Graph Theory. 33, 337-346
N. Dehgardi, S. M. Sheikholeslami and L. Volkmann The rainbow domination subdivision numbers of graphs. Mat. Vesnik, (to appear).
M. Falahat, S. M. Sheikholeslami and L. Volkmann (2014). New bounds on the rainbow domination subdivision number. Filomat. 28, 615-622
T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in graphs. Marcel Dekker, Inc., New York.
T. W. Haynes, M. A. Henning and P. J. Slater (2003). Strong equality of domination parameters in trees. Discrete Math.. 260, 77-87
T. W. Haynes, M. A. Henning and P. J. Slater (2001). Strong equality of upper domination and independence in trees. Util. Math.. 59, 111-124
T. W. Haynes and P. J. Slater (1998). Paired-domination in graphs. Networks. 32, 199-206
S. M. Sheikholeslami and L. Volkmann (2012). The $k$-rainbow domatic number of a graph. Discuss. Math. Graph Theory. 32, 129-140
D. B. West (2000). Introduction to Graph Theory. Prentice-Hall, Inc..