The 3-rainbow index of graph operations

Abstract

A tree $T$, in an edge-colored graph $G$, is called {\em a rainbow tree} if no two edges of $T$ are assigned the same color. A {\em $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 {\em $k$-rainbow index of $G$}, denoted by $r{x}_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^{\ast }=G_1\square G_2\cdots \square G_k$ ($k\ge 2$), where each $G_i$ is connected, then $r{x}_3(G^{\ast })\le {\sum }_{i=1}^{k}r{x}_3(G_i)$. Moreover, we also present a condition and show the above equality holds if every graph $G_i(1\le i\le 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.

10 pages,6 figures. arXiv admin note: text overlap with arXiv:1101.5747 by other authors

References in corpus (3)

• Rainbow Connection Number and Connected Dominating Sets
• Some upper bounds for 3-rainbow index of graphs
• A note on the 3-rainbow index of $K_{2,t}$