Rainbow vertex-connection and graph products. Issue 7 (2nd July 2016) - Mao, Yaping; Yanling, Fengnan; Wang, Zhao; Ye, Chengfu
Abstract : A vertex-coloured 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 colours, such a path is called a rainbow path. The rainbow vertex-connection number of a connected graph G, denoted by r v c ( G ), is the smallest number of colours that are needed in order to make G rainbow vertex-connected. In this paper, we study the rainbow vertex-connection number on the lexicographical, strong, Cartesian and direct product and present several upper bounds for these products of graphs. The rainbow vertex-connection number of some product networks is also investigated in this paper.