The rainbow vertex-index of complementary graphs

Abstract

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)\leq 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\subseteq 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\subseteq V'$. For $S\subseteq V(G)$ and $|S|\geq 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 $rvx_k(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.
Received: 12 April 2015 | Accepted: 31 May 2015