Rainbow vertex-connection and graph products. Issue 7 (2nd July 2016)

• Record Type: Journal Article
• Authors: Mao, Yaping; Yanling, Fengnan; Wang, Zhao; Ye, Chengfu
• Is Part Of: International journal of computer mathematics. Volume 93:Issue 7(2016)
• Page Start: 1078
• Page End: 1092
• Publication Date: 2016-07-02
• Subjects: vertex-colouring -- rainbow vertex-connection number -- direct product -- lexicographic product -- Cartesian product -- strong product; 05C15 -- 05C40 -- 05C76; Computers -- Periodicals; Numerical analysis -- Periodicals; Automation -- Periodicals; 004.0151
• DOI: 10.1080/00207160.2015.1047356
• Languages: English
• ISSNs: 0020-7160

Abstract

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.