The rainbow vertex-index of complementary graphs

A vertex-colored graph g is rainbow vertex-connected if two vertices are connected by a path whose internal vertices have distinct colors. 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 vertices 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 0;e0) of g that is a tree with s ⊆ v 0. for s ⊆ v (g) and isi ≥ 2, an s-steiner tree t is said to be a rainbow vertex s-tree if the internal vertices of t receive distinct colors. the minimum number of colors that are needed in a 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). in this paper, we first investigate the strong rainbow vertex-connection of complementary graphs. the k-rainbow vertex-index of complementary graphs are also studied.