2012/01/07 by Li, Xueliang, Mao, Yaping, Shi, Yongtang
#05C15 #05C40 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1201.1541
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)≤ 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≤ srvc(G)≤ 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≥ 5 and b≥ (7a-8)/5, there exists a connected graph G such that rvc(G)=a and srvc(G)=b.