Unicyclic graphs with strong equality between the 2-rainbow domination and independent 2-rainbow domination numbers
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 $vin V$ with $f(v)=emptyset$ the condition $bigcup_{uin N(v)}f(u)={1,2}$ is fulfilled. A 2RDF $f$ is independent (I2R...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Isfahan
2015-06-01
|
| Series: | Transactions on Combinatorics |
| Subjects: | |
| Online Access: | http://www.combinatorics.ir/pdf_6518_70bb50bdb82bf7fe7c4d75610adbf9cd.html |
| Summary: | 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 $vin V$ with $f(v)=emptyset$ the
condition $bigcup_{uin N(v)}f(u)={1,2}$ is fulfilled. A 2RDF $f$ is
independent (I2RDF) if no two vertices assigned nonempty sets are adjacent.
The emph{weight} of a 2RDF $f$ is the value $omega(f)=sum_{vin V}|f (v)|$.
The 2-emph{rainbow domination number} $gamma_{r2}(G)$ (respectively, the
emph{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)$. |
|---|---|
| ISSN: | 2251-8657 2251-8665 |