WSEAS Transactions on Mathematics
Print ISSN: 1109-2769, E-ISSN: 2224-2880
Volume 13, 2014
The 3-Rainbow Index of Graph Operations
Authors: ,
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 ⊆ 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. Firstly, let $$G_{i}(i = 1, 2, · · · , k)$$ be connected graphs and $$G^{∗}$$ be the Cartesian product of $$G_{i}$$. That is to say, $$G^{∗} = G_{1}G_{2} · · · G_{k} (k ≥ 2).$$ Then we proved that $$rx_{3}(G^{∗}) ≤ Σ_{i=1}^{k} rx_{3}(G_{i})$$. And we also get the condition when the equality holds. As a corollary, we obtain an upper bound for the 3-rainbow index of strong product graph. Secondly, we discuss the 3-rainbow index of the lexicographic graph G[H] for connected graphs G and H. And the sharp upper bound is given. Finally, we consider some other simple graph operations : the join of two graphs, split a vertex of a graph and subdivide an edge of a graph. The upper bounds of the 3-rainbow index of the three operation graphs are presented, respectively.
Search Articles
Pages: 161-170
WSEAS Transactions on Mathematics, ISSN / E-ISSN: 1109-2769 / 2224-2880, Volume 13, 2014, Art. #17