120
Views
5
CrossRef citations to date
0
Altmetric
Original Articles

Rainbow vertex-connection and graph products

, , &
Pages 1078-1092 | Received 28 Jan 2015, Accepted 16 Apr 2015, Published online: 02 Jun 2015
 

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(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.

2010 AMS Subject Classifications:

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].

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.