@article{article_168453, title={The rainbow vertex-index of complementary graphs}, journal={Journal of Algebra Combinatorics Discrete Structures and Applications}, volume={2}, pages={157–161}, year={2015}, DOI={10.13069/jacodesmath.80607}, author={Yanling, Fengnan and Wang, Zhao and Ye, Chengfu and Zhang, Shumin}, keywords={Strong rainbow vertex-connection number, Complementary graph, Rainbow vertex S-tree, k-rainbowvertex-index}, abstract={<p>A vertex-colored graph $G$ is \emph{rainbow vertex-connected} if two <br />vertices are connected by a path whose internal vertices have <br />distinct colors. The \emph{rainbow vertex-connection number} of a <br />connected graph $G$, denoted by $rvc(G)$, is the smallest number of <br />colors that are needed in order to make $G$ rainbow <br />vertex-connected. If for every pair $u,v$ of distinct vertices, $G$ <br />contains a vertex-rainbow $u-v$ geodesic, then $G$ is \emph{strongly <br />rainbow vertex-connected}. The minimum $k$ for which there exists a <br />$k$-coloring of $G$ that results in a strongly <br />rainbow-vertex-connected graph is called the \emph{strong rainbow <br />vertex number} $srvc(G)$ of $G$. Thus $rvc(G)\leq srvc(G)$ for every <br />nontrivial connected graph $G$. A tree $T$ in $G$ is called a <br />\emph{rainbow vertex tree} if the internal vertices of $T$ receive <br />different colors. For a graph $G=(V,E)$ and a set $S\subseteq V$ of <br />at least two vertices, \emph{an $S$-Steiner tree} or \emph{a Steiner <br />tree connecting $S$} (or simply, \emph{an $S$-tree}) is a such <br />subgraph $T=(V’,E’)$ of $G$ that is a tree with $S\subseteq V’$. For <br />$S\subseteq V(G)$ and $|S|\geq 2$, an $S$-Steiner tree $T$ is said <br />to be a \emph{rainbow vertex $S$-tree} if the internal vertices of $T$ receive distinct colors. The minimum number of colors that are <br />needed in a vertex-coloring of $G$ such that there is a rainbow <br />vertex $S$-tree for every $k$-set $S$ of $V(G)$ is called the {\it <br />$k$-rainbow vertex-index} of $G$, denoted by $rvx_k(G)$. In this <br />paper, we first investigate the strong rainbow vertex-connection of <br />complementary graphs. The $k$-rainbow vertex-index of complementary graphs are also studied. </p>}, number={3}, publisher={iPeak Academy}