# The 3-rainbow index of graph operations

TINGTING LIU Tianjin University Department of Mathematics 300072 Tianjin CHINA
<EMAIL_ADDRESS>YUMEI HU111corresponding author Tianjin University Department
of Mathematics 300072 Tianjin CHINA<EMAIL_ADDRESS>

Abstract: A tree $T$, in an edge-colored graph $G$, is called a rainbow tree
if no two edges of $T$ are assigned the same color. A $k$-rainbow coloring of
$G$ is an edge coloring of $G$ having the property that for every set $S$ of
$k$ vertices of $G$, there exists a rainbow tree $T$ in $G$ such that
$S\subseteq V(T)$. The minimum number of colors needed in a $k$-rainbow
coloring of $G$ is the $k$-rainbow index of $G$, denoted by $rx_{k}(G)$. Graph
operations, both binary and unary, are an interesting subject, which can be
used to understand structures of graphs. In this paper, we will study the
$3$-rainbow index with respect to three important graph product operations
(namely cartesian product, strong product, lexicographic product) and other
graph operations. In this direction, we firstly show if $G^{*}=G_{1}\Box
G_{2}\cdots\Box G_{k}$ ($k\geq 2$), where each $G_{i}$ is connected, then
$rx_{3}(G^{*})\leq\sum_{i=1}^{k}rx_{3}(G_{i})$. Moreover, we also present a
condition and show the above equality holds if every graph $G_{i}~{}(1\leq
i\leq k)$ meets the condition. As a corollary, we obtain an upper bound for
the 3-rainbow index of strong product. Secondly, we discuss the 3-rainbow
index of the lexicographic graph $G[H]$ for connected graphs $G$ and $H$. The
proofs are constructive and hence yield the sharp bound. Finally, we consider
the relationship between the 3-rainbow index of original graphs and other
simple graph operations : the join of $G$ and $H$, split a vertex of a graph
and subdivide an edge. Key–Words: $3$-rainbow index; cartesian product; strong
product; lexicographic product.

##  1 Introduction

All graphs considered in this paper are simple, connected and undirected. We
follow the terminology and notation of Bondy and Murty [7]. Let $G$ be a
nontrivial connected graph of order $n$ on which is defined an edge coloring,
where adjacent edges may be the same color. A path $P$ is a rainbow path if no
two edges of $P$ are colored the same. The graph $G$ is rainbow connected if
$G$ contains a $u$-$v$ rainbow path for every pair $u,v$ of distinct vertices
of $G$. If by coloring $c$ the graph $G$ is rainbow connected , the coloring
$c$ is called a rainbow coloring of $G$. The rainbow connection number $rc(G)$
of $G$, introduced by Chartrand et al. in [5], is the minimum number of colors
that results in a rainbow connected graph $G$.

Rainbow connection has an interesting application for the secure transfer of
classified information between agencies (cf. [2]). Although the information
needs to be protected since it is vital to national security, procedures must
be in place that permit access between appropriate parties. This two fold
issues can be addressed by assigning information transfer paths between
agencies which may have other agencies as intermediaries while requiring a
large enough number of passwords and firewalls that is prohibitive to
intruders, yet small enough to manage (that is, enough so that one or more
paths between every pair of agencies have no password repeated). An immediate
question arises: What is the minimum number of passwords or firewalls needed
that allows one or more secure paths between every two agencies so that the
passwords along each path are distinct? This situation can be modeled by a
graph and studied by the means of rainbow coloring.

Later, another generalization of rainbow connection number was introduced by
Chartrand et al.[4] in 2009. A tree $T$ is a rainbow tree if no two edges of
$T$ are colored the same. Let $k$ be a fixed integer with $2\leq k\leq n$. An
edge coloring of $G$ is called a $k$-rainbow coloring if for every set $S$ of
$k$ vertices of $G$, there exists a rainbow tree in $G$ containing the
vertices of $S$. The $k$-rainbow index $rx_{k}(G)$ of $G$ is the minimum
number of colors needed in a $k$-rainbow coloring of $G$. It is obvious that
$rc(G)=rx_{2}(G)$. A tree $T$ is called a concise tree if $T$ contains $S$ and
$T-v$ is not a tree containing $S$, where $v$ is any vertex of $T$. In the
paper, we suppose the tree containing $S$ be concise. Since if the given tree
$T$ is not concise, we can get a concise tree by deleting some vertices from
$T$.

As we know, the diameter is a natural lower bound of the rainbow connection
number. Similarly, we consider the Steiner diameter in this paper, which is a
nice generalization of the concept of diameter. The Steiner distance $d(S)$ of
a set $S$ of vertices in $G$ is the minimum size of a tree in $G$ containing
$S$. Such a tree is called a Steiner S-tree or simply a Steiner tree. The
$k$-Steiner diameter $sdiam_{k}(G)$ of $G$ is the maximum Steiner distance of
$S$ among all sets $S$ with $k$ vertices in $G$. The $k$-Steiner diameter
provides a lower bound for the $k$-rainbow index of $G$, i.e.,
$sdiam_{k}(G)\leq rx_{k}(G)$. It follows, for every nontrivial connected graph
$G$ of order $n$, that

$rx_{2}(G)\leq rx_{3}(G)\leq\cdots\leq rx_{k}(G).$

For general $k$, Chartrand et al. [4] determined the $k$-rainbow index of
trees and cycles. They obtained the following theorems.

###### Theorem 1.1

[4] Let $T$ be a tree of order $n\geq 3$. For each integer $k$ with $3\leq
k\leq n$,

$rx_{k}(T)=n-1.$

###### Theorem 1.2

[4] For integers $k$ and $n$ with $3\leq k\leq n$,

$rx_{k}(C_{n})=\left\\{\begin{array}[]{lll}n-2,&\mbox{ if~{} $k=3$ and $n\geq
4$;}\\\ n-1,&\mbox{ if~{} $k=n=3$ or $4\leq k\leq n$.}\\\ \end{array}\right.$

In the paper, we focus our attention on $rx_{3}(G)$. For 3-rainbow index of a
graph, Chartrand et al. [4] derive the exact value for the complete graphs.

###### Theorem 1.3

[4] For any integer $n\geq 3$,

$rx_{3}(K_{n})=\left\\{\begin{array}[]{lll}2,&\mbox{ if~{} $3\leq n\leq
5$;}\\\ 3,&\mbox{ if~{} $n\geq 6$;}\\\ \end{array}\right.$

Chakraborty et al. [11] showed that computing the rainbow connection number of
a graph is NP-hard. So it is also NP-hard to compute $k$-rainbow index of a
connected graph. For rainbow connection number $rc(G)$, people aim to give
nice upper bounds for this parameter, especially sharp upper bounds, according
to some parameters of the graph $G$ [9, 18, 19, 25].

Many researchers have paid more attention to rainbow connection number of some
graph products [10, 12, 16, 20, 21]. There is one way to bound the rainbow
connection number of a graph product by the rainbow connection number of the
operand graphs. Li and Sun [21] adopted the method to study rainbow connection
number with respect to Cartesian product and lexicographic product. They got
the following conclusions.

###### Theorem 1.4

[21] Let $G^{*}=G_{1}\Box G_{2}\cdots\Box G_{k}$ ($k\geq 2$), where each
$G_{i}$ is connected, then

$rc(G^{*})\leq\sum_{i=1}^{k}rc(G_{i})$

Moreover, if $rc(G_{i})=diam(G_{i})$ for each $G_{i}$, then the equality
holds.

###### Theorem 1.5

[21] If $G$ and $H$ are two graphs and $G$ is connected, then we have
1\. if $H$ is complete, then

$rc(G[H])\leq rc(G).$

In particular, if $diam(G)=rc(G)$, then $rc(G[H])=rc(G)$.
2\. if $H$ is not complete,then

$rc(G[H])\leq rc(G)+1.$

In particular, if $diam(G)=rc(G)$, then $diam$$(G[H])=2$ if $G$ is complete
and $rc(G)\leq diam(G)+1$ if $G$ is not complete.

In this paper, we study the $3$-rainbow index with respect to three important
graph product operations (namely cartesian product, lexicographic product and
strong product) and other operations of graphs. Moreover, we present the class
of graphs which obtain the upper bounds.

###  1.1 Preliminaries

We use $V(G)$, $E(G)$ for the set of vertices and edges of $G$, respectively.
For any subset $X$ of $V(G)$, let $G[X]$ be the subgraph induced by $X$, and
$E[X]$ the edge set of $G[X]$; Similarly, for any subset $E^{\prime}$ of
$E(G)$, let $G[E^{\prime}]$ be the subgraph induced by $E^{\prime}$. For any
two disjoint subsets $X$, $Y$ of $V(G)$, we use $G[X,Y]$ to denote the
bipartite graph with vertex set $X\cup Y$ and edge set $E[X,Y]=\\{uv\in
E(G)|u\in X,v\in Y\\}$. The distance between two vertices $u$ and $v$ in $G$
is the length of a shortest path between them and is denoted by $d_{G}(u,v)$.
The distance between a vertex $u$ and a path $P$ is the shortest distance
between $u$ and the vertices in $P$. Given a graph $G$, the eccentricity of a
vertex, $v\in V(G)$ is given by $ecc(v)=max\\{d_{G}(v,u):u\in V(G)\\}$. The
diameter of $G$ is defined as $diam(G)=max\\{ecc(v):v\in V(G)\\}$. The length
of a path is the number of edges in that path. The length of a tree $T$ is the
numbers of edges in that tree, denoted by $size(T)$. $G\setminus e$ denotes
the graph obtained by deleting an edge $e$ from the graph $G$ but leaving the
vertices and the remaining edges intact. $G-v$ denotes the graph obtained by
deleting the vertex $v$ together with all the edges incident with $v$ in $G$.

###### Definition 1

(The Cartesian Product) Given two graphs $G$ and $H$, the Cartesian product of
$G$ and $H$, denoted by $G\Box H$, is defined as follows: $V(G\Box
H)=V(G)\times V(H)$. Two distinct vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$
of $G\Box H$ are adjacent if and only if either $g_{1}=g_{2}$ and
$h_{1}h_{2}\in E(H)$ or $h_{1}=h_{2}$ and $g_{1}g_{2}\in E(G)$.

###### Definition 2

(The Lexicographic Product) The Lexicographic Product $G[H]$ of graphs $G$ and
$H$ has the vertex set $V(G[H])=V(G)\times V(H)$. Two vertices
$(g_{1},h_{1}),(g_{2},h_{2})$ are adjacent if $g_{1}g_{2}\in E(G)$, or if
$g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$.

###### Definition 3

(The Strong Product) The Strong Product $G\boxtimes H$ of graphs $G$ and $H$
is the graph with $V(G\boxtimes H)=V(G)\times V(H)$. Two distinct vertices
$(g_{1},h_{1})$ and $(g_{2},h_{2})$ of $G\boxtimes H$ are adjacent whenever
$g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$ or $h_{1}=h_{2}$ and $g_{1}g_{2}\in
E(G)$ or $g_{1}g_{2}\in E(G)$ and $h_{1}h_{2}\in E(H)$.

Clearly, the resultant graph is isomorphic to $G$ (respectively $H$) if
$H=K_{1}$ (respectively $G=K_{1}$). Therefore, we suppose $V(G)\geq 2$ and
$V(H)\geq 2$ when studying the 3-rainbow index of these three graph products.

###### Definition 4

(The union of graphs) The union of two graphs, by starting with a disjoint
union of two graphs $G$ and $H$ and adding edges joining every vertex of $G$
to every vertex of $H$, the resultant graph is the join  of $G$ and $H$,
denoted by $G\vee H$.

###### Definition 5

(To split a vertex) To split a vertex $v$ of a graph $G$ is to replace $v$ by
two adjacent vertices $v_{1}$ and $v_{2}$, and to replace each edge incident
to $v$ by an edge incident to either $v_{1}$ or $v_{2}$ (but not both), the
other end of the edge remaining unchanged.

###  1.2 Some basic observations

It is easy to see that if the graph $H$ has a $3$-rainbow coloring with
$rx_{3}(H)$ colors, then the graph $G$, which is obtained from $H$ by adding
some edges to $H$, also has a $3$-rainbow coloring with $rx_{3}(H)$ colors
since the new edges of $G$ can be colored arbitrarily with the colors used in
$H$. So we have:

###### Observation 1

Let $G$ and $H$ be connected graphs and $H$ be a spanning subgraph of $G$.
Then $rx_{3}(G)\leq rx_{3}(H)$.

To verify a 3-rainbow index, we need to find a rainbow tree containing any set
of three vertices. So it is necessary to know the structure of concise trees.
Next we consider the structure of concise trees $T$ containing three vertices,
which will be very useful in the sequel.

###### Observation 2

Let $G$ be a connected graph and $S=\\{v_{1},v_{2},v_{3}\\}\subseteq V(G)$. If
$T$ is a concise tree containing $S$, then $T$ belongs to exactly one of Type
$I$ and Type $II$( see Figure 1).
Type $I$: $T$ is a path such that one vertex of $S$ as its origin, one of $S$
as its terminus, other vertex of $S$ as its internal vertex.
Type $II$: $T$ is a tree obtained from the star $S_{3}$ by replacing each edge
of $S_{3}$ with a path $P$.

Figure 1: Two types of concise trees, where
$\\{v_{i_{1}},v_{i_{2}},v_{i_{3}}\\}=\\{v_{1},v_{2},v_{3}\\}$, $v_{4}\in V(G)$

Proof: Firstly, we claim that the leaves of $T$ belong to $S$. Since if there
exists a leaf $v$ such that $v\notin S$, then we can get the more minimal tree
$T^{\prime}=T-v$ containing $S$, a contradiction. Thus the $T$ has at most
three leaves. If the $T$ has exactly two leaves, then it is easy to verify
that $T$ is a path. In this case, $T$ belongs to Type $I$. Otherwise there is
a $v_{1}v_{2}$-path $P$ in $T$ such that $v_{3}\notin P$. Since $T$ is
connected, there a path $P^{\prime}$ in $T$ connecting $v_{3}$ and $P$. Let
$v_{4}$ be the vertex of $P^{\prime}$ such that
$d_{T}(v_{3},v_{4})$=$d_{T}(v_{3},P)$. Then we get $T\supseteq P\cup
P^{\prime}$. On the other hand, we know, $P\cup P^{\prime}$ is a tree
containing $S$. Furthermore, since $T$ is a concise tree, $T=P\cup
P^{\prime}$, which belongs to Type $II$. $\sqcap\\!\\!\\!\\!\sqcup$

##  2 Cartesian product

In this section, we do some research on the relationship between the
$3$-rainbow index of the original graphs and that of the cartesian products.
Recall that the Cartesian product of $G$ and $H$, denoted by $G\Box H$, is
defined as follows: $V(G\Box H)=V(G)\times V(H)$. Two distinct vertices
$(g_{1},h_{1})$ and $(g_{2},h_{2})$ of $G\Box H$ are adjacent if and only if
either $g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$ or $h_{1}=h_{2}$ and
$g_{1}g_{2}\in E(G)$. Let $V(G)=\\{g_{i}\\}_{i\in[s]}$,
$V(H)=\\{h_{j}\\}_{j\in[t]}$. Note that $H_{i}=G\Box
H[\\{(g_{i},h_{j})\\}_{j\in[t]}]\cong H,G_{j}=G\Box
H[\\{(g_{i},h_{j})\\}_{i\in[s]}]\cong G$. Any edge
$(g_{i},h_{j_{1}})(g_{i},h_{j_{2}})$ of $H_{i}$ corresponds to edge
$h_{j_{1}}h_{j_{2}}$ of $H$ and $(g_{i_{1}},h_{j})(g_{i_{2}},h_{j})$ of
$G_{j}$ corresponds to edge $g_{i_{1}}g_{i_{2}}$ of $G$. For the sake of our
results, we give some useful and fundamental conclusions about the Cartesian
product.

###### Lemma 2.1

[17] The Cartesian product of two graphs is connected if and only if these two
graphs are both connected.

###### Lemma 2.2

[17] The Cartesian product is associative.

###### Lemma 2.3

[17] Let $(g_{1},h_{1})$ and $(g_{2},h_{2})$ be arbitrary vertices of the
Cartesian product $G\Box H$. Then

$d_{G\Box
H}((g_{1},h_{1}),(g_{2},h_{2}))=d_{G}(g_{1},g_{2})+d_{H}(h_{1},h_{2}).$

With the aid of Observation 2 and above Lemmas, we derive the following lemma,
which is useful to show the sharpness of our main result.

###### Lemma 2.4

Let $G^{*}=G_{1}\Box G_{2}\cdots\Box G_{k}$ ($k\geq 2$), where each $G_{i}$ is
connected. Then

$Sdiam_{3}(G^{*})=\sum_{i=1}^{k}Sdiam_{3}(G_{i}).$

Proof: We first prove the conclusion holds for the case $k=2$. Let $G=G_{1}$,
$H=G_{2}$, $V(G)=\\{g_{i}\\}_{i\in[s]}$, $V(H)=\\{h_{j}\\}_{j\in[t]}$,
$V(G^{*})=\\{g_{i},h_{j}\\}_{i\in[s],j\in[t]}=\\{v_{i,j}\\}_{i\in[s],j\in[t]}$.
Let
$S=\\{(g_{1},h_{1}),(g_{2},h_{2}),(g_{3},h_{3})\\},S_{1}=\\{g_{1},g_{2},g_{3}\\},S_{2}=\\{h_{1},h_{2},h_{3}\\}$
be a set of any three vertices of $V(G^{*})$, $V(G)$, $V(H)$, respectively.
Suppose that $T$, $T_{1}$ and $T_{2}$ be Steiner trees containing $S$,
$S_{1}$, $S_{2}$, respectively. Next, we only need to show
$size(T)$=$size(T_{1})$+$size(T_{2})$.

On the one hand, by the definition of the Cartesian product of graphs, each
edge of $G^{*}$ is exactly one element of $\\{H_{i},G_{j}\\}$,
$i\in[s],j\in[t]$. Then we can regard $T$ as the union $G^{\prime}$ and
$H^{\prime}$, where $G^{\prime}$ is induced by all the edges of $G_{j}\cap T$,
$j\in[t]$, $H^{\prime}$ is induced by all the edges of $H_{i}\cap T$,
$i\in[s]$. Let $G^{\prime\prime}$ and $H^{\prime\prime}$ be the graphs induced
by the corresponding edges of all edges of $G_{j}\cap T$ and $H_{i}\cap
T$($i\in[s],j\in[t]$) in $G$ and $H$, respectively. Clearly,
$G^{\prime\prime}$ and $H^{\prime\prime}$ are connected and containing $S_{1}$
and $S_{2}$, respectively. Hence, we have,
$size(T)$=$size(G^{\prime})$+$size(H^{\prime})$=$size(G^{\prime\prime})$+$size(H^{\prime\prime})$
$\geq$ $size(T_{1})$+$size(T_{2})$.

On the other hand, we try to construct a tree $T^{\prime}$ containing $S$ with
$size(T^{\prime})=$ $size(T_{1})$+$size(T_{2})$. Notice that, for every
subgraph in $G$ (or $H$), we can find the corresponding subgraph in any copy
$G_{j}$ ( or $H_{i}$). If $T_{1}$ or $T_{2}$ belongs to Type $I$, without loss
of generality, say $T_{1}=P_{1}\cup P_{2}$, where $P_{1}$ is the path
connecting $g_{i_{1}}$ and $g_{i_{2}}$, $P_{2}$ is the path connecting
$g_{i_{2}}$ and $g_{i_{3}}$,
$\\{g_{i_{1}},g_{i_{2}},g_{i_{3}}\\}=\\{g_{1},g_{2},g_{3}\\}$. We can find a
tree $T^{\prime}=P_{1}^{\prime}\cup T_{2}^{\prime}\cup P_{2}^{\prime}$
containing $S$, where the path $P_{1}^{\prime}$ is the corresponding path of
$P_{1}$ in $G_{i_{1}}$ and the path $P_{2}^{\prime}$ is the corresponding path
of $P_{2}$ in $G_{i_{3}}$, the tree $T_{2}^{\prime}$ is the corresponding tree
of $T_{2}$ in $H_{i_{2}}$, (see Figure 2).

Figure 2 : $T_{1}$ belongs to Type $I$

If not, that is to say, $T_{1}$, $T_{2}$ belong to Type $II$, we suppose
$T_{1}=P_{1}\cup P_{2}\cup P_{3}$, where $P_{i}$ is the path connecting
$g_{4}$ and $g_{i}$ ($1\leq i\leq 3$), $g_{4}$ is other vertex of $G$ except
the vertices of $S_{1}$. Then the tree $T^{\prime}=P_{1}^{\prime}\cup
P_{2}^{\prime}\cup P_{3}^{\prime}\cup T_{2}^{\prime}$ containing $S$ can also
be found in $G\Box H$, where $P_{i}^{\prime}$ is the corresponding path of
$P_{i}$ in $G_{i}$ ($1\leq i\leq 3$), the $T_{2}^{\prime}$ is the
corresponding tree of $T_{2}$ in $H_{4}$ (see Figure $3$). Thus, $size(T)\leq$
$size(T^{\prime})$=$size(T_{1})$+$size(T_{2})$.

Figure 3 : $T_{1}$ and $T_{2}$ belong to Type $II$.

So we get $size(T)$=$size(T_{1})$+$size(T_{2})$. Hence, $Sdiam_{3}(G_{1}\Box
G_{2})$= $Sdiam_{3}(G_{1})$+$Sdiam_{3}(G_{2})$. By Lemma 2.2,
$Sdiam_{3}(G^{*})$= $Sdiam_{3}(G_{1}\Box G_{2}$ $\Box\cdots$ $\Box
G_{k-1})$+$Sdiam_{3}(G_{k})$=$\sum_{i=1}^{k}$ $Sdiam_{3}(G_{i})$.
$\sqcap\\!\\!\\!\\!\sqcup$

###### Theorem 2.1

Let $G^{*}=G_{1}\Box G_{2}\cdots\Box G_{k}$ ($k\geq 2$), where each $G_{i}$ is
connected, then

$rx_{3}(G^{*})\leq\sum_{i=1}^{k}rx_{3}(G_{i})$

Moreover, if $rx_{3}(G_{i})=Sdiam_{3}(G_{i})$ for each $G_{i}$, then the
equality holds.

Proof: We first show the conclusion holds for the case $k=2$. Let $G=G_{1}$,
$H=G_{2}$, $V(G)=\\{g_{i}\\}_{i\in[s]}$, $V(H)=\\{h_{j}\\}_{j\in[t]}$,
$V(G^{*})=\\{g_{i},h_{j}\\}_{i\in[s],j\in[t]}=\\{v_{i,j}\\}_{i\in[s],j\in[t]}$.
Since $G$ and $H$ are connected, $G^{*}$ is connected by Lemma 2.1. For
example, Figure $4$ shows the case for $G=P_{4}$ and $H=P_{3}$.

Figure 4 : An example in Theorem 2.1.

Since for an edge $v_{i_{1},j_{1}}v_{i_{2},j_{2}}\in G^{*}$, we have
$i_{1}=i_{2}$ or $j_{1}=j_{2}$; if the former, then
$v_{i_{1},j_{1}}v_{i_{1},j_{2}}\in H_{i_{1}}$, otherwise,
$v_{i_{1},j_{1}}v_{i_{2},j_{1}}\in G_{j_{1}}$. Hence, we only give a coloring
of each graph $G_{j}~{}(j\in[t])$ and $H_{i}~{}(i\in[s])$.

We give $G$ a $3$-rainbow coloring with $rx_{3}(G)$ colors (see Figure 4 in
which $G$ obtains a $3$-rainbow coloring with colors 1, 2, 3), and $H$ a
$3$-rainbow coloring with $rx_{3}(H)$ fresh colors (see Figure 4 in which $H$
obtains a 3-rainbow coloring with other two fresh colors, 4, 5). Then we color
edges of $G^{*}$ as follow: if the edge belongs to some $H_{i}$, then assign
the edge with the same color with its corresponding edge of $H$ (for example,
edge $v_{1,1}v_{1,2}$ belong to $H_{1}$ and corresponds to the edge
$h_{1}h_{2}$ in $H$, so it receives the color $4$), otherwise, the edge
belongs to some $G_{j}$, then assign the edge with the same color with its
corresponding edge of $G$. Now we will show that the given coloring is
$3$-rainbow coloring of $G^{*}$. It suffices to show that for every set $S$ of
three vertices of $G^{*}$, there is a rainbow tree containing $S$. Let
$S=\\{(g_{1},h_{1}),(g_{2},h_{2}),(g_{3},h_{3})\\}$. we distinguish three
cases:

Case 1 The vertices of $S$ lie in some $G_{j}$ (or $H_{i}$), where
$i,j\in\\{1,2,3\\}$

That is, $g_{1}=g_{2}=g_{3}$ or $h_{1}=h_{2}=h_{3}$, without loss of
generality, we say, $g_{1}=g_{2}=g_{3}$. Under the given coloring of $H$, we
can find a rainbow tree $T$ containing $h_{1},~{}h_{2},~{}h_{3}$ in $H$. By
the strategy of the above coloring, the corresponding tree $T^{\prime}$ of $T$
in $H_{1}$ is also rainbow and contains $S$.

Case 2 The vertices of $S$ lie in two different copies $G_{j}^{\prime}$
,$G_{j}^{\prime\prime}$ (or $H_{i}^{\prime}$, $H_{i}^{\prime\prime}$). where
$j^{\prime},~{}j^{\prime\prime}\in\\{1,~{}2,~{}3\\}$(or
$i^{\prime},i^{\prime\prime}\in\\{1~{},2,~{}3\\}$.

Without loss of generality, we assume $g_{1}=g_{2}\neq g_{3}$. Note that if a
coloring is $3$-rainbow coloring, then it is also rainbow coloring, that is,
there is a rainbow path connecting any two vertices of graphs. If $h_{1}\neq
h_{2}\neq h_{3}$ ($h_{1}=h_{3}\neq h_{2}$ or $h_{2}=h_{3}\neq h_{1}$), we can
find a rainbow tree $T_{1}$ in $H$ containing $h_{1},h_{2},h_{3}$
($h_{1},h_{2}$). By the strategy of coloring, we can find a rainbow tree
$T_{1}^{\prime}$ in $H_{1}$ containing $\\{v_{1,1},v_{2,2},v_{1,3},\\}$
($\\{v_{1,1},v_{2,2}\\}$). So we can find a rainbow path $P_{1}^{\prime}$ in
$G_{3}$ connecting $v_{1,3}$ ($v_{1,1}$ or $v_{2,2}$) and $v_{3,3}$. Thus
there is a rainbow tree $T=T_{1}^{\prime}\cup P_{1}^{\prime}$ in $G\Box H$
containing $S$.

Case 3 The vertices of $S$ lie in three different copies $G_{1}$, $G_{2}$,
$G_{3}$ and $H_{1}$, $H_{2}$, $H_{3}$.

Let $T_{1}$ be a rainbow tree containing $g_{1},g_{2},g_{3}$ and $T_{2}$ be a
rainbow tree containing $h_{1},h_{2},h_{3}$.

If $T_{1}$ or $T_{2}$ belongs to Type $I$, say $T_{1}$, let $T_{1}=P_{1}\cup
P_{2}$. Then the tree $T=P_{1}^{\prime}\cup T_{2}^{\prime}\cup P_{2}^{\prime}$
containing $S$ can be constructed by the way of Figure $2$. And by the
character of the given coloring, the tree $T$ is a rainbow tree.

If $T_{1}$ and $T_{2}$ belong to Type $II$, let $T_{1}=P_{1}\cup P_{2}\cup
P_{3}$. Then the tree $T=P_{1}^{\prime}\cup P_{2}^{\prime}\cup
P_{3}^{\prime}\cup T_{2}^{\prime}$ can also be obtained by the way of Figure
$3$. Furthermore, it is easy to see that the it is also a rainbow tree.

Since we use $rx_{3}(G)+rx_{3}(H)$ colors totally, we have $rx_{3}(G^{*})\leq
rx_{3}(G)+rx_{3}(H)$. From Lemma 2.4, if $rx_{3}(G)=Sdiam_{3}(G)$ and
$rx_{3}(H)=Sdiam_{3}(H)$, then
$Sdiam_{3}(G^{*})=Sdiam_{3}(G)+Sdiam_{3}(H)=rx_{3}(G)+rx_{3}(H)\geq
rx_{3}(G^{*})$. On the other hand, $Sdiam_{3}(G^{*})\leq rx_{3}(G^{*})$, so
the conclusion holds for $k=2$.

For general $k$, by the Lemma 2.2, $rx_{3}(G^{*})=rx_{3}(G_{1}\Box
G_{2}\Box\cdots\Box G_{k-1}\Box G_{k})\leq rx_{3}(G_{1}\Box G_{2}\Box$
$\cdots\Box G_{k-1})+rx_{3}(G_{k})\leq\sum_{i=1}^{k}rx_{3}(G_{i})$. Moreover,
if $rx_{3}(G)=Sdiam_{3}(G_{i})$ for each $G_{i}$, then $rx_{3}(G^{*})\geq
Sdiam_{3}(G^{*})=\sum_{i=1}^{k}Sdiam_{3}(G_{i})=\sum_{i=1}^{k}rx_{3}(G_{i})\geq
rx_{3}(G^{*})$. So if $rx_{3}(G_{i})=Sdiam_{3}(G_{i})$ for each $G_{i}$, then
the equality holds. $\sqcap\\!\\!\\!\\!\sqcup$

###### Corollary 2.1

Let $G=P_{n_{1}}\Box P_{n_{2}}\Box\cdots\Box P_{n_{k}}$, where $P_{n_{i}}$ is
a path with $n_{i}$ vertices ($1\leq i\leq k$). Then

$rx_{3}(G)=\sum_{i=1}^{k}n_{i}-k.$

Proof: For every path $P_{n_{i}}$, by Theorem 1.1, we have
$Sdiam_{3}(P_{n_{i}})=rx_{3}(P_{n_{i}})=n_{i}-1$. Thus, by the Theorem 2.1,
$rx_{3}(G)=\sum_{i=1}^{k}rx_{3}(P_{n_{i}})=\sum_{i=1}^{k}n_{i}-k$.
$\sqcap\\!\\!\\!\\!\sqcup$

Recall that the strong product $G\boxtimes H$ of graphs $G$ and $H$ has the
vertex set $V(G)\times V(H)$. Two vertices $(g_{1},h_{1})$ and $(g_{2},h_{2})$
are adjacent whenever $g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$ or $h_{1}=h_{2}$
and $g_{1}g_{2}\in E(G)$ or $g_{1}g_{2}\in E(G)$ and $h_{1}h_{2}\in E(H)$. By
the definition, the graph $G\Box H$ is the spanning subgraph of the graph
$G\boxtimes H$ for any graphs $G$ and $H$. With the help of Observation 1,
then we have the following result.

###### Corollary 2.2

Let $\overline{G^{*}}$ =$G_{1}\boxtimes G_{2}\boxtimes\cdots\boxtimes G_{k}$,
$(k\geq 2)$, where each $G_{i}~{}(1\leq i\leq k)$ is connected. Then we have

$rx_{3}(\overline{G^{*}})\leq\sum_{i=1}^{k}rx_{3}(G_{i}).$

##  3 Lexicographic Product

Recall that the lexicographic product $G[H]$ of graphs $G$ and $H$ has the
vertex set $V(G[H])=V(G)\times V(H)$. Two vertices
$(g_{1},h_{1}),(g_{2},h_{2})$ are adjacent if $g_{1}g_{2}\in E(G)$, or if
$g_{1}=g_{2}$ and $h_{1}h_{2}\in E(H)$. By definition, $G[H]$ can be obtained
from $G$ by submitting a copy $H_{1}$ for every $g_{1}\in V(G)$ and by joining
all vertices of $H_{1}$ with all vertices of $H_{2}$ if $g_{1}g_{2}\in E(G)$.

In this section, we consider the relationship between 3-rainbow index of the
original graphs and their lexicographic product. Since the rainbow connection
and 3-rainbow index is only defined in connected graphs, it is nature to
assume the original graphs are connected. Note that if $V(G)=1$ (or $V(H)=1$),
then $G[H]$=$H$ (or $G$). So in the following discussion, we suppose $V(G)\geq
2$ and $V(H)\geq 2$. By definition, if $G$ and $H$ are complete, then $G[H]$
is also complete.

So for some special cases of $G$ and $H$, we have the following lemma.

###### Lemma 3.1

If $G,H\cong K_{2}$, then

$rx_{3}(G[H])=2.$

If $G$ and $H$ are complete with $V(G)\geq 3$ or $V(H)\geq 3$, then

$rx_{3}(G[H])=3.$

Proof: If $G,H\cong K_{2}$, then $G[H]$=$K_{4}$. Hence, we have
$rx_{3}(G[H])=2$ by Theorem 1.3. If $G$ and $H$ are complete with $V(G)\geq 3$
or $V(H)\geq 3$, then $G[H]=K_{n}$ ($n\geq 6$). We get immediately
$rx_{3}(G[H])=3$ from the Theorem 1.3. $\sqcap\\!\\!\\!\\!\sqcup$

For the remaining cases, we obtain the following theorem.

###### Theorem 3.1

Let $G$ and $H$ be two connected graphs with $V(G)\geq 2$, $V(H)\geq 2$, and
at least one of $G$, $H$ be not complete. Then

$rx_{3}(G[H])\leq rx_{3}(G)+rc(H).$

In particular, if $diam(G)=rx_{3}(G)$, and $H$ is complete, then the equality
holds.

Proof: Let $V(G)=\\{g_{i}\\}_{i\in[s]}$, $V(H)=\\{h_{j}\\}_{j\in[t]}$,
$V(G[H])=\\{g_{i},h_{j}\\}_{i\in[s],j\in[t]}=\\{v_{i,j}\\}_{i\in[s],j\in[t]}$.
Let $S=\\{(g_{1},h_{1}),(g_{2},h_{2}),(g_{3},h_{3})\\}$ be any three different
vertices of $G[H]$. We derive the theorem from two parts: 1\. $V(H)=2$ and $G$
is not complete; 2\. $V(H)\geq 3$ and $G$ or $H$ is not complete.

1\. If $V(H)=2$ and $G$ is not complete, we firstly give $G$ a $3$-rainbow
coloring with $rx_{3}(G)$ colors. Then we can give $G[H]$ a $rx_{3}(G)$+1-edge
coloring as follows: the edge belongs to some $G_{j}$, then assign the edge
with the same color with its corresponding edge in $G$. Otherwise, assign the
edge a fresh color.

If $h_{1}=h_{2}=h_{3}$, then we can find a rainbow tree $T^{\prime}$
containing $S$ , which is the corresponding tree of $T$ containing
$g_{1},~{}g_{2},~{}g_{3}$ in $G_{1}$. Otherwise the vertices of $S$ lie in two
different graphs $G_{1}$ and $G_{2}$. Without loss of generality, we suppose
$h_{1}=h_{3}\neq h_{2}$. In this case, $(g_{1},h_{1}),(g_{3},h_{3})\in G_{1}$,
$(g_{2},h_{2})\in G_{2}$. Then we can find the corresponding vertex
$(g_{2},h_{1})$ (or $(g_{1},h_{1})$ or $(g_{3},h_{3})$) of $(g_{2},h_{2})$ in
$H_{1}$ and a rainbow tree $T^{\prime}$ containing
$(g_{1},h_{1}),(g_{3},h_{3})$ and $(g_{2},h_{1})$ (or $\emptyset$). Clearly,
there is a rainbow tree $T=T^{\prime}\cup e$ containing $S$, where
$e=(g_{2},h_{2})(g_{2},h_{1})$ (or $(g_{1},h_{1})$ or $(g_{3},h_{3})$). Hence
the above coloring is $3$-rainbow coloring of $G[H]$. So $rx_{3}(G[H])\leq
rx_{3}(G)+1=rx_{3}(G)+rc(H)$.

2\. Let $c_{1}=\\{0,1,\cdots,rx_{3}(G)-1\\}$ be a $3$-rainbow coloring of $G$.
Let $c_{2}$ be a rainbow coloring of $H$ using $rc(H)$ fresh colors. For every
$h_{j}\in H$ color the copy $G_{j}$ the same as $G$. By the same way, there is
a rainbow tree containing any three vertices
$(g_{1},h_{i}),(g_{2},h_{i}),(g_{3},h_{i})\in V(G[H])$. Every edge of the form
$(g_{1},h_{1})(g_{2},h_{2})$ get color $k+1$ mod($rx_{3}(G))$, where
$g_{1}g_{2}\in E(G)$, $h_{1}\neq h_{2}$, and $c_{1}(g_{1}g_{2})=k$. Finally,
color edges from $H_{i}$ the same as $H$ such that any two vertices
$(g_{i},h_{j})(g_{i},h_{k})$ are connected by a rainbow path. The figure $5$
shows an example of the coloring.

Figure 5 : An example in Theorem 3.1. 2.

Now we show the above coloring is $3$-rainbow coloring of $G[H]$. We
distinguish the following three cases.

Case 1 $g_{1}=g_{2}=g_{3}$

Since $G$ is a connected graph, there exists an edge $g_{1}g_{4}\in
E(G),g_{4}\in V(G)$. Then we can find a rainbow path $P$ connecting
$(g_{2},h_{2})(g_{1},h_{1})$ in $H_{1}$, which uses the colors of $H$. By the
coloring of strategy, the tree $T=P\cup v_{1,1}v_{4,1}\cup v_{4,1}v_{3,3}$ is
a rainbow tree containing $S$.

Case 2 $g_{1}=g_{2}\neq g_{3}$ or $g_{1}=g_{3}\neq g_{2}$ or $g_{2}=g_{3}\neq
g_{1}$

Without loss of generality, we assume $g_{1}=g_{2}\neq g_{3}$.

Subcase 2.1 $h_{1}=h_{3}$ (or $h_{2}=h_{3}$)

Then $T=P_{1}\cup P_{2}$ is a rainbow tree containing $S$, where $P_{1}$ is a
rainbow path connecting $(g_{1},h_{1})$ and $(g_{2},h_{2})$ in $H_{1}$,
$P_{2}$ is a rainbow path connecting $(g_{1},h_{1})$ (or $(g_{2},h_{2})$) and
$(g_{3},h_{3})$ in $G_{3}$.

Subcases 2.2 $h_{1}\neq h_{2}\neq h_{3}$

As we know, there is a rainbow path $P_{1}$ connecting $g_{3}$ and $g_{1}$ in
$G$. The case that $P_{1}$=$g_{3}g_{1}$ is trivial, so we assume
$P_{1}$=$g_{3}g_{1}^{\prime}$$g_{2}^{\prime},$$\cdots,g_{k}^{\prime}g_{1}$,
$g_{i}^{\prime}\in V(G)$ $(1\leq i\leq k)$. We claim that
$P_{1}^{\prime}=(g_{3},h_{3})(g_{1}^{\prime},h_{2})(g_{2}^{\prime},h_{3})(g_{3}^{\prime},h_{2}),\cdots,(g_{k}^{\prime},u)(g_{1},h_{1})$
is a rainbow path connecting $(g_{3},h_{3})$ and $(g_{1},h_{1})$, where
$u=h_{3}$ if $k$ is even and $u=h_{2}$ otherwise. It is easy to see that the
path only use the edge of the form $(g_{i},h_{j})(g_{j},h_{l})$, where
$g_{i}g_{j}\in E(G)$, $h_{j}\neq h_{l}$. By the character of coloring, the
path is also a rainbow path and only uses the colors of $G$. Thus, there is a
rainbow tree $T=P^{\prime}\cup P_{2}$ containing $S$, where $P_{2}$ is a
rainbow path connecting $(g_{1},h_{1})$ and $(g_{2},h_{2})$ in $H_{1}$.

Case 3 $g_{1}\neq g_{2}\neq g_{3}$

Subcase 3.1 $h_{1}=h_{2}=h_{3}$

Then the $S$ lie in the copy $G_{1}$. So by the given coloring, we can claim
there is a rainbow tree $T$ containing $S$.

Subcase 3.2 $h_{1}=h_{2}\neq h_{3}$ or $h_{1}=h_{3}\neq h_{2},$ or
$h_{2}=h_{3}\neq h_{1}$

We suppose $h_{1}=h_{2}\neq h_{3}$. In this case, we first find the
corresponding vertex $(g_{3},h_{1})$ of $(g_{3},h_{3})$ in $G_{1}$. Then there
is a rainbow tree $T^{\prime}$ containing
$(g_{1},h_{1})(g_{2},h_{2})(g_{3},h_{1})$ in $G_{1}$ and a rainbow path $P$
connecting $(g_{3},h_{1})(g_{3},h_{3})$ in $H_{3}$. Thus, the rainbow tree
$T=T^{\prime}\cup P$ is our desire tree.

Subcase 3.3 $h_{1}\neq h_{2}\neq h_{3}$

Suppose $T_{1}$ be a rainbow tree containing $g_{1},g_{2},g_{3}$.

If $T_{1}$ or $T_{2}$ belongs to Type $I$, without loss of generality, we say
$T_{1}$. In order to describe graphs simply, we might suppose the leaves of
$T_{1}$ are $g_{1}$ and $g_{3}$, $T_{1}=P_{1}\cup P_{2}$, where $P_{1}$ is a
rainbow path connecting $g_{1}$ and $g_{2}$, $P_{2}$ is a rainbow path
connecting $g_{2}$ and $g_{3}$. If $P_{1}$ or $P_{2}$ is an edge, it is
trivial. So we suppose $P_{1}=g_{1}g_{1}^{\prime}g_{2}^{\prime}$ $\cdots
g_{k}^{\prime}$ $g_{2}$ and
$P_{2}=g_{2}g_{1}^{\prime\prime}g_{2}^{\prime\prime}$ $\cdots
g_{l}^{\prime\prime}g_{3}$. Thus we can construct a rainbow tree
$T_{1}^{\prime}=P_{1}^{\prime}\cup P_{2}^{\prime}$ containing $S$, where
$P_{1}^{\prime}=(g_{1},h_{1})$$(g_{1}^{\prime},h_{3})(g_{2}^{\prime},h_{1})$
$\cdots$ $(g_{k}^{\prime},u)(g_{2},h_{2})$,
$P_{2}^{\prime}=(g_{2},h_{2})(g_{1}^{\prime\prime},h_{1})(g_{2}^{\prime\prime},h_{2})$
$\cdots(g_{l}^{\prime\prime},v)(g_{3},h_{3})$, $u=h_{3}$, if $k$ is odd,
$u=h_{1}$ otherwise; $v=h_{1}$, if $l$ is odd; $v=h_{2}$ otherwise.

If $T_{1}$ and $T_{2}$ belong to Type $II$, suppose $T_{1}=P_{1}\cup P_{2}\cup
P_{3}$ and $T_{2}=Q_{1}\cup Q_{2}\cup Q_{3}$, where $P_{i},Q_{i}~{}(1\leq
i\leq 3)$ is a rainbow path connecting $g_{4}$ and $g_{i}$, $h_{4}$ and
$h_{i}$. If $P_{i}~{}(1\leq i\leq 3)$ is an edge, then it is trivial. Now we
suppose $P_{i}$ ($1\leq i\leq 3$) are not edges, then
$P_{1}$=$g_{4}l_{1}^{\prime}$$l_{2}^{\prime}\cdots l_{k}^{\prime}g_{1}$,
$P_{2}=g_{4}l_{1}^{\prime\prime}l_{2}^{\prime\prime}\cdots
l_{p}^{\prime\prime}g_{2}$, $P_{3}$=
$g_{4}l_{1}^{\prime\prime\prime}l_{2}^{\prime\prime\prime}\cdots
l_{q}^{\prime\prime\prime}g_{3}$. Similarly, the corresponding rainbow tree
$T_{1}^{\prime}=P_{1}^{\prime}\cup P_{2}^{\prime}\cup P_{3}^{\prime}$ can be
obtained containing $S$, where
$P_{1}^{\prime}=(g_{4},h_{4})(l_{1}^{\prime},h_{2})$
$(l_{2}^{\prime},h_{4})\cdots(l_{k}^{\prime},u_{1})$ $(g_{1},h_{1})$,
$P_{2}^{\prime}=(g_{4},h_{4})$$(l_{1}^{\prime\prime},h_{3})$
$(l_{2}^{\prime\prime},h_{4})\cdots(l_{p}^{\prime\prime},u_{2})$
$(g_{2},h_{2})$, $P_{3}=(g_{4},h_{4})(l_{1}^{\prime\prime\prime},h_{2})$
$(l_{2}^{\prime\prime\prime},h_{4})\cdots(l_{q}^{\prime\prime\prime},u_{3})(g_{3},h_{3})$,
$u_{1},u_{3}=h_{2},$ $u_{2}=h_{3}$ if $k,p,q$ is odd,
$u_{1},u_{2},u_{3}=h_{4}$, otherwise.

From the above discussion, we have, the given coloring is $3$-rainbow coloring
and we use $rx_{3}(G)+rc(H)$ colors totally. Thus, $rx_{3}(G[H])\leq
rx_{3}(G)+rc(H)$.

If $diam(G)=rx_{3}(G)$, and $H$ is complete, then $rx_{3}(G[H])\leq
rx_{3}(G)+rc(H)=diam(G)+1$. On the other hand, let $g,g^{\prime}\in V(G)$ such
that $d_{G}(g,g^{\prime})=diam(G)$. Let
$S=\\{(g^{\prime},h),(g,h)(g,h^{\prime})\\}$. By the Lemma 2.3,it is easy to
check that the tree containing $S$ has size at least $diam(G)+1$. So
$rx_{3}(G[H])\geq Sdiam_{3}(G[H])\geq diam(G)+1$. Thus,
$rx_{3}(G[H])=rx_{3}(G)+rc(H)$. $\sqcap\\!\\!\\!\\!\sqcup$

##  4 Other graph operations

We first consider the union of two graphs. Recall that the union of two
graphs, by starting with a disjoint union of two graphs $G$ and $H$ and adding
edges jointing every vertex of $G$ to every vertex of $H$, the resultant graph
is the join of $G$ and $H$, denoted by $G\vee H$. Note that if
$E(G)=\emptyset$ and $E(H)=\emptyset$, then the resultant graph is complete
bipartite graph. So we need some results about the 3-rainbow index of complete
bipartite graph. Li et al. got the following theorem for regular complete
bipartite graphs $K_{r,r}$.

###### Lemma 4.1

[8] For integer $r$ with $r\geq 3$, $rx_{3}(K_{r,r})=3$.

For complete bipartite graph, we obtained the following Lemmas.

###### Lemma 4.2

[14] For any complete bipartite graphs $K_{s,t}$ with $3\leq s\leq t$,
$rx_{3}(K_{s,t})\leq min\\{6,s+t-3\\}$, and the bound is tight.

In the proof of above Lemma 4.2, we showed the claim that for any $s\geq 3$,
$t\geq 2\times 6^{s}$, $rx_{3}(K_{s,t})=6$.

###### Lemma 4.3

[15] For any integer $t\geq 2$,

$rx_{3}(K_{2,t})=\left\\{\begin{array}[]{lll}2,&\mbox{ if ~{}~{}$t=2$;}\\\
3,&\mbox{ if ~{}~{}$t=3,4$;}\\\ 4,&\mbox{ if ~{}~{}$5\leq t\leq 8$;}\\\
5,&\mbox{ if ~{}~{}$9\leq t\leq 20$;}\\\ k,&\mbox{ if ~{}~{}$C_{k-1}^{2}+1\leq
t\leq C_{k}^{2}$,~{}($k\geq 6$).}\\\ \end{array}\right.$

Then, we derive the relationship between the $3$-rainbow index of the original
two graphs and that of their join graph. Note that if $G$ and $H$ are both
complete graphs, then $G\vee H$ is also the complete graph. By the Theorem
1.3, $rx_{3}(G\vee H)=3$ if $|V(G)|$+$|V(H)|$$\geq 6$; $rx_{3}(G\vee H)=2$ if
$|V(G)|$+$|V(H)|\leq 5$. So we consider the remaining cases in following
theorem.

###### Theorem 4.1

If $G$, $H$ are connected and at least one of $G$, $H$ are not complete, with
$|V(G)|=s$, $|V(H)|=t$, $s\leq t$, then we have
1\. if $s=1$, then

$rx_{3}(G\vee H)\leq rx_{3}(H)+1.$

2\. if $2=s\leq t$, then

$rx_{3}(G\vee H)\leq min\\{rc(H)+3,rx_{3}(K_{2,t})\\}.$

3\. if $3\leq s\leq t$, then

$rx_{3}(G\vee H)\leq min\\{c_{1}+1,rx_{3}(K_{s,t})\\}$

Where $c_{1}=max\\{rx_{3}(G),rx_{3}(H)\\}$.
In particular, if $s=t\geq 3$, then $rx_{3}(G\vee H)=rx_{3}(K_{s,t})=3$.

Proof: Let $G^{\prime}=G\vee H$, $V(G^{\prime})=V_{1}\cup V_{2}$ such that
$G^{\prime}[V_{1}]\cong G$, $G^{\prime}[V_{2}]\cong H$, where
$V_{1}=\\{v_{1},v_{2},\cdots,v_{s}\\}$,
$V_{2}=\\{u_{1},u_{2},\cdots,u_{t}\\}$.

1\. If $s=1$, then $G^{\prime}[V_{1}]$ is singleton vertex, we give an edge
coloring of $G^{\prime}$ as follows : we first give a 3-rainbow coloring of
$G^{\prime}[V_{2}]$ using $rx_{3}(H)$ colors. And for the other edges, that
is, elements of $E[V_{1},V_{2}]$, we use a fresh color. It is easy to show the
above coloring of $G^{\prime}$ is 3-rainbow coloring.

2\. If $2=s\leq t$, then $G^{\prime}[V_{1},V_{2}]\cong K_{2,t}$ is a spanning
subgraph of $G^{\prime}$. We have $rx_{3}(G^{\prime})\leq
rx_{3}(G^{\prime}[V_{1},V_{2}])=rx_{3}(K_{2,t})$. On the other hand, we give
an edge coloring of $G^{\prime}$ as follows: we first color the edges of the
subgraph $G^{\prime}[V_{2}]$ with $rc(H)$ colors such that it is rainbow
connected; we give the elements of $E[V_{1},V_{2}]$ incident with
$v_{i}$($i=1,2$) with color $rc(H)+i$ ($i=1,2$); for the element of
$G^{\prime}[V_{1}]$, we use a fresh color $rc(H)+3$. It is easy to show the
above coloring of $G^{\prime}$ is 3-rainbow coloring. Thus, we have
$rx_{3}(G\vee H)\leq min\\{rc(H)+3,rx_{3}(K_{2,t})\\}$.

3\. If $3\leq s\leq t$, by Lemma 4.2, we have $rx_{3}(G^{\prime})\leq
rx_{3}(G^{\prime}[V_{1},V_{2}])=rx_{3}(K_{s,t})$, similarly. On the other
hand, we color the edges of $G^{\prime}$ as follows: we first color the edges
of the subgraph $G^{\prime}[V_{i}]$ with $c_{1}$ colors such that it is
3-rainbow coloring of $G^{\prime}[V_{i}]$ ($i=1,2$). For the rest edges, that
is, elements of $E[V_{1},V_{2}]$, we use a fresh color $c_{1}+1$. It is easy
to verify that the coloring is a $3$-rainbow coloring. Thus, we get
$rx_{3}(G\vee H)\leq min\\{rx_{3}(K_{s,t}),c_{1}+1\\}$.

If $s=t\geq 3$, by Lemma 4.1, then $rx_{3}(G^{\prime})\leq rx_{3}(K_{s,s})=3$;
On the other hand, by Observation 1 and Theorem 1.3, $rx_{3}(G^{\prime})\geq
rx_{3}(K_{s+t})=3$, so the conclusion holds.

Note that $rx_{3}(K_{2,t})$ may be larger than $rc(H)+3$; for example, we
choose $H\cong K_{t}\setminus e~{}(t\geq 21)$. Then
$rx_{3}(K_{2,t})>5=rc(H)+3$ by Lemma 4.3. But $rx_{3}(K_{2,t})$ is not always
larger than $rc(H)+3$; for example, we choose $H\cong P_{t}~{}$, then
$rx_{3}(K_{2,t})<t+2=rc(H)+3$. Moreover, $rx_{3}(K_{s,t})~{}(3\leq s<t)$ may
be larger than $max\\{rx_{3}(G),rx_{3}(H)\\}+1$, since we suppose $G\cong
K_{s}\setminus e~{}(s\geq 3)$ and $H\cong K_{t}$, where $t\geq 2\times 6^{s}$.
Then $rx_{3}(K_{s,t})=6>max\\{rx_{3}(G),rx_{3}(H)\\}+1$. But $rx_{3}(K_{s,t})$
is not always larger than $max\\{rx_{3}(G),rx_{3}(H)\\}+1$. Similarly, for
example, $G,H\cong P_{s}$ ($s\geq 7$), we can get
$max\\{rx_{3}(G),rx_{3}(H)\\}+1=s>6\geq rx_{3}(K_{s,t})$. So the bounds we
give in the theorem are reasonable. $\sqcap\\!\\!\\!\\!\sqcup$

Recall that to split $v$ of a graph $G$ is to replace $v$ by two adjacent
vertices $v_{1}$ and $v_{2}$ by an edge incident to either $v_{1}$ or $v_{2}$
(but not both), the other end of the edge remaining unchanged. The Figure $6$
shows the operation of $G$. Let $N_{G}(v)$ be the neighbor sets of $v$. The
set is partitioned into two disjoint sets $N_{1}$ and $N_{2}$ such that
$N_{1}$ and $N_{2}$ are the neighbor sets of $v_{1}$ and $v_{2}$ in the
resultant graph, respectively.

Figure 6 : The operation for vertex spliting.

###### Theorem 4.2

If $G$ is a connected graph and $G^{\prime}$ is obtained from $G$ by splitting
a vertex $v$, then

$rx_{3}(G^{\prime})\leq rx_{3}(G)+1.$

Proof: We first give $G$ a $3$-rainbow coloring with $rx_{3}(G)$ colors, then
we give $G^{\prime}$ a $rx_{3}(G)$+1-edge coloring as follows: we give the
edge $e=v_{1}v_{2}$ a color $rx_{3}(G)$+1; for any edge $uv_{1}\in G^{\prime}$
with $uv_{1}\neq e$, let the color of $uv_{1}$ be the same as that of $uv$ in
$G$; for any edge $v_{2}w\in G^{\prime}$ with $v_{2}w\neq e$, let the color of
$v_{2}w$ be the same as that of $vw$ in $G$; color of the rest edges of
$G^{\prime}$ are the same as in $G$. Next, we will show the given coloring of
$G^{\prime}$ is a 3-rainbow coloring. It suffices to show that there is a
rainbow tree containing any three vertices of $G^{\prime}$. Let
$S=\\{x,y,z\\}$.

Case 1 Two vertices of $S$ belongs to $\\{v_{1},v_{2}\\}$, say $x=v_{1}$,
$y=v_{2}$.

By the above coloring, there a rainbow $v-z$ path $P:v=u_{1},\cdots,u_{t}=z$.
If $u_{2}\in N_{1}$, then $P^{\prime}:v_{1},u_{2},u_{3},\cdots,u_{t}=z$ is a
rainbow connecting $z$ and $x(v_{1})$. Thus, $T=P^{\prime}\cup e$ is the
rainbow tree containing $S$. If $u_{2}\in N_{2}$, it is similar to verify that
there is a rainbow tree containing $S$.

Case 2 Exactly one of $S$ belongs to $\\{v_{1},v_{2}\\}$, say $x=v_{1}$.

We know that, in graph $G$, there is a rainbow tree $T_{1}$ containing
$y,z,v$.

subcase 2.1 $d_{T_{1}}(v)=1$.

Then there is an edge $uv\in E(T_{1})$. If $u\in N_{1}$, the tree obtained
from $T_{1}$ by replacing $v$ with $v_{1}$ is rainbow and contains $S$. If
$u\in N_{2}$, the tree obtained from $T_{1}$ by replacing $v$ with
$v_{2},~{}v_{1}$ is a rainbow tree containing $S$.

subcase 2.2 $d_{T_{1}}(v)\neq 1$.

From the Observation 2, we claim $d_{T_{1}}(v)=2$. Let $u_{1}$ and $u_{2}$ be
the two neighbors of $v$ in $T_{1}$. If $u_{1}$ and $u_{2}$ belong to the
$N_{1}$, then let $T$ be obtained from $T_{1}$ by replacing $v$ with $v_{1}$.
If $u_{1}$ and $u_{2}$ belong to the $N_{2}$, then we can find a rainbow tree
$T=T_{2}\cup e$, where $T_{2}$ is obtained from $T_{1}$ by replacing $v$ with
$v_{2}$. If $u_{1}$ and $u_{2}$ belong to the different $N_{i}~{}(i=1,2)$,
then $T$ obtained from $T_{1}$ by replacing $v$ with subgraph $v_{1}v_{2}$ is
rainbow.

Case 3 None of vertices in $S$ belongs to $\\{v_{1},v_{2}\\}$.

We know that there is a rainbow $T_{3}$ containing $S$ in $G$. If $v$ does not
belong to $T_{3}$, then $T_{3}$ is also a rainbow tree containing $S$ in
$G^{\prime}$.

If $v$ belong to the tree $T_{3}$, by the Observation 2, then
$d_{T_{3}}(v)=2,~{}3$. Similar to the Subcase 2.2, we can find a rainbow tree
containing $S$.

So $G^{\prime}$ receives a 3-rainbow coloring. Since we use $rx_{3}(G)+1$
colors totally, then $rx_{3}(G^{\prime})\leq rx_{3}(G)+1$.
$\sqcap\\!\\!\\!\\!\sqcup$

A special case of vertex splitting occurs when exactly one link is assigned to
either $v_{1}$ or $v_{2}$. The resulting graph can be viewed as having been
obtained by subdividing an edge of the original graph, where to subdivide an
edge is to delete $e$, add a new vertex $x$, and join $x$ to the ends of $e$.
So by Theorem 4.2, we have

###### Corollary 4.1

If $G$ is a connected graph, and $G^{\prime}$ is obtained from $G$ by
subdividing an edge $e$, then

$rx_{3}(G^{\prime})\leq rx_{3}(G)+1.$

##  5 Conclusion

Rainbow connection number $rc(G)$ ($rx_{2}(G)$) comes from the communication
of information between agencies of government. $3$-rainbow index, $rx_{3}(G)$,
is a generalization of rainbow connection number. Chakraborty et al. have
proved that computing $rc(G)$($rx_{2}(G)$) is NP-hard. Hence, To get the exact
value for 3-rainbow index of general graph $G$ is also NP-hard. Thus,
researchers tend to get some better upper for 3-rainbow index of some classes
of graphs. Graph operations, both binary and unary, are interesting subjects,
which can be used to understand structures of graphs. In this paper, we will
study the $3$-rainbow index with respect to three important graph product
operations (namely cartesian product, strong product, lexicographic product)
and other graph operations. In this direction, we firstly show if
$G^{*}=G_{1}\Box G_{2}\cdots\Box G_{k}$ ($k\geq 2$), where each $G_{i}$ is
connected, then $rx_{3}(G^{*})\leq\sum_{i=1}^{k}rx_{3}(G_{i})$. Moreover, we
also present a condition and show the above equality holds if every graph
$G_{i}~{}(1\leq i\leq k)$ meets the condition. As a corollary, we obtain an
upper bound for the 3-rainbow index of strong product. Secondly, we discuss
the 3-rainbow index of the lexicographic graph $G[H]$ for connected graph $G$
and $H$. The proofs are constructive and hence yield the sharp bound. Finally,
we consider the relationship between the 3-rainbow index of original graphs
and other simple graph operations : the join of $G$ and $H$, split a vertex of
a graph and subdivide an edge and get the upper bounds.

Acknowledgements: The corresponding author, Yumei Hu, is supported by NSFC No.
11001196.

## References:

  * [1]
  * [2] A. B. Ericksen, A matter of scurity, Graduating Engineer and Computer Careers, 2007, pp. 24–28.
  * [3] B. Reed, Paths, stars, and the number three, Combinatorics, Probability Computing 5, 1996, pp. 277–295.
  * [4] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55, 2010, pp. 360–367.
  * [5] G. Chartrand, G. L. Johns, K. A. MeKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem 133, 2008, pp. 85–98.
  * [6] I. E. Zverovich, Perfect connected-dominant graphs. Discuss. Math. Graph Theory 23, 2003, pp. 159–162.
  * [7] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
  * [8] L. Chen, X. Li, K. Yang, Y. Zhao, The 3-rainbow index of a graph, Discuss. Math. Graph Theory, in press. arXiv:1307.0079V3 [math.CO] (2013).
  * [9] L. S. Chand, A. Das, D. Rajendraprasad, N. M. Varma, Rainbow connection number and connected dominating sets, Electronic Notes in Discrete Math. 38, 2011, pp. 239–244.
  * [10] M. Basavaraju, L. S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number of graph power and graph products, Graphs and Combin., in press. DOI: 10.1007/s00373-013-1355-3
  * [11] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connection, J. Combin. Optim. 21, 2010, pp. 330–347.
  * [12] S. Kla$\breve{v}$ar, G. Meki, On the rainbow connection of Cartesian products and their subgraphs, Discuss. Math. Graph Theory 32, 2012, pp. 783-793.
  * [13] S. Li, X. Li, W. Zhou, Sharp bounds for the generalized connectivity $\kappa_{3}(G)$, Discrete Math. 310, 2010, pp. 2147–2163.
  * [14] T, Liu, Y, Hu, Some upper bounds for 3-rainbow index of graphs, arXiv:1310.2355V1 [math.CO], 2013.
  * [15] T, Liu, Y, Hu, A note on the 3-rainbow index of $K_{2,t}$, arXiv:1310.2353V1 [math.CO] (2013).
  * [16] T. Gologranca, G. Meki$\breve{s}$, I. Peterin, Rainbow connection and graph products, Graphs and Combin., in press. DOI: 10.1007/s00373-013-1295-y
  * [17] W. Imrich, S. Kla$\breve{v}$zar, B. Gorenec, Product graphs: structure and recognition, Wiley, New York 2000\.
  * [18] X. Li, S. Liu, Rainbow Connections number and the number of blocks, Graphs and Combin., in press. DOI: 10.1007/s00373-013-1369-x
  * [19] X. Li, Y. Shi, Y. Sun, Rainbow connections of graphs—A survey, Graphs and Combin 29, 2013, pp. 1–38.
  * [20] X. Li, Y. Sun, Rainbow connection numbers of line graphs, Ars Combin. 100, 2011, pp. 449–463.
  * [21] X. Li, Y. Sun, Characterize graphs with rainbow connection number $m$-2 and rainbow connection numbers of some graph operations, Preprint (2010).
  * [22] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin 15, 2008, R57.
  * [23] Y. Shang, A sharp threshold for rainbow connection in small-world networks, Miskolc Math. Notes 13, 2012, pp. 493–497.
  * [24] Y. Shang, A sharp threshold for rainbow connection of random bipartite graphs, Int. J. Appl. Math. 24, 2011, pp. 149–153.
  * [25] Y. Sun, On Two Variants of Rainbow Connection, WSEAS TRANSACTIONS on MATHEMATICS 12, 2013, pp. 266–276.