Rainbow Connectivity Of Graph Operations

A vertex-colored graph G is said to be rainbow vertex-connected if every two vertices of G are connected by a path whose internal vertices have distinct colors, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. If for every pair u, v of distinct vertices, G contains a vertex-rainbow u- v geodesic, then G is strongly rainbow vertex-connected.The minimum k for which there exists a k-coloring of G that results in a strongly rainbow-vertex-connected graph is called the strong rainbow vertex number srvc(G)of G. Thus rvc(G) ≤ srvc(G) for every nontrivial connected graph G. A tree T in G is called a rainbow vertex tree if the internal vertexes of T receive different colors.For a graph G =(V, E) and a set S ? V of at least two vertices, an S-Steiner tree or a Steiner tree connecting S(or simply, an S-tree) is a such subgraph T =(V, E)of G that is a tree with S ? V. For S ? V(G) and |S| ≥ 2, an S-Steiner tree T is said to be a rainbow vertex S-tree if the internal vertice of T receive distict colors.The minimum number of colors that are needed in an vertex-coloring of G such that there is a rainbow vertex S-tree for every k-set S of V(G) is called the k-rainbow vertex-index of G, denoted by rvxk(G). For a positive integer k, an vertex-colouring of a graph G is rainbow vertex k-connected if any two vertices of G are connected by k internally vertex-disjoint rainbow vertex paths. The rainbow vertex k-connection number rvck(G) is defined to be the minimum integer t such that there exists an vertexcolouring of G with t colours which is rainbow vertex k-connected. An edge-coloured path is rainbow if the colours of its edges are distinct. A tree T in G is called a rainbow tree if no two edges of T receive the same color. For a graph G =(V, E) and a set S ? V of at least two vertices, an S-Steiner tree is a such subgraph T =(V, E) of G that is a tree with S ? V. For S ? V(G) and |S| ≥ 2, an S-Steiner tree T is said to be a rainbow S-tree if no two edges of T receive the same color. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for every k-set S of V(G) is called the k-rainbow index of G, denoted by rxk(G).In chaper 1, we introduce the background and the symbols in this paper. In chaper2, we study the rainbow vertex-connectivity of direct product, lexicographic product,Cartesian product, strong product, and obtain some upper bounds of rainbow vertexconnectivity. We also investigate the strong rainbow vertex-connectivity of some wellknown networks. In chaper 3, we investigate the 3-rainbow index of complementary multipartite graph, 3-rainbow index and strong rainbow vertex-connectivity of complementary graph, k-rainbow vertex-index of complementary multipartite graph, krainbow vertex-index of graph operations. In chaper 4, we consider rvc2(G) when G has fixed vertex-connectivity.