Rainbow vertex-connection and graph products

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 $rvc\left(G\right)$, 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.

Keywords:

• vertex-colouring
• rainbow vertex-connection number
• direct product
• lexicographic product
• Cartesian product
• strong product

2010 AMS Subject Classifications:

• 05C15
• 05C40
• 05C76

Acknowledgements

The authors are very grateful to the referees' valuable comments and suggestions, which helped greatly to improve the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Funding

Supported by the National Science Foundation of China [Nos. 11161037, 11101232, 11461054] and the Science Found of Qinghai Province [No. 2014-ZJ-907].