The strong rainbow vertex-connection of graphs

Abstract

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 rainbow $u-v$ geodesic, then $G$ is strong rainbow vertex-connected. The minimum number $k$ for which there exists a $k$-vertex-coloring of $G$ that results in a strongly rainbow vertex-connected graph is called the strong rainbow vertex-connection number of $G$, denoted by $srvc(G)$. Observe that $rvc(G)\le srvc(G)$ for any nontrivial connected graph $G$. In this paper, sharp upper and lower bounds of $srvc(G)$ are given for a connected graph $G$ of order $n$, that is, $0\le srvc(G)\le n-2$. Graphs of order $n$ such that $srvc(G)=1,2,n-2$ are characterized, respectively. It is also shown that, for each pair $a,b$ of integers with $a\ge 5$ and $b\ge (7a-8)/5$, there exists a connected graph $G$ such that $rvc(G)=a$ and $srvc(G)=b$.

10 pages