The rainbow vertex-index of complementary graphs

Abstract

A vertex-colored graph $G$ is \emph{rainbow vertex-connected} if twovertices are connected by a path whose internal vertices havedistinct colors. The \emph{rainbow vertex-connection number} of aconnected graph $G$, denoted by $rvc(G)$, is the smallest number ofcolors that are needed in order to make $G$ rainbowvertex-connected. If for every pair $u,v$ of distinct vertices, $G$contains a vertex-rainbow $u-v$ geodesic, then $G$ is \emph{stronglyrainbow vertex-connected}. The minimum $k$ for which there exists a$k$-coloring of $G$ that results in a stronglyrainbow-vertex-connected graph is called the \emph{strong rainbowvertex number} $srvc(G)$ of $G$. Thus $rvc(G)\leq srvc(G)$ for everynontrivial connected graph $G$. A tree $T$ in $G$ is called a\emph{rainbow vertex tree} if the internal vertices of $T$ receivedifferent colors. For a graph $G=(V,E)$ and a set $S\subseteq V$ ofat least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steinertree connecting $S$} (or simply, \emph{an $S$-tree}) is a suchsubgraph $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 saidto be a \emph{rainbow vertex $S$-tree} if the internal vertices of $T$ receive distinct colors. The minimum number of colors that areneeded in a vertex-coloring of $G$ such that there is a rainbowvertex $S$-tree for every $k$-set $S$ of $V(G)$ is called the {\it$k$-rainbow vertex-index} of $G$, denoted by $rvx_k(G)$. In thispaper, we first investigate the strong rainbow vertex-connection ofcomplementary graphs. The $k$-rainbow vertex-index of complementary graphs are also studied.