Article ID Journal Published Year Pages File Type
419945 Discrete Applied Mathematics 2013 7 Pages PDF
Abstract

Let kk be a positive integer and GG be a kk-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow  kk-connection number   of GG, denoted by rck(G)rck(G), is the minimum number of colours required to colour the edges of GG so that any two vertices of GG are connected by kk internally vertex-disjoint rainbow paths. The function rck(G)rck(G) was first introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted considerable interest. In this paper, we consider a version of the function rck(G)rck(G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex  kk-connection number   of GG, denoted by rvck(G)rvck(G), is the minimum number of colours required to colour the vertices of GG so that any two vertices of GG are connected by kk internally vertex-disjoint vertex-rainbow paths. We shall study the function rvck(G)rvck(G) when GG is a cycle, a wheel, and a complete multipartite graph. We also construct graphs GG where rck(G)rck(G) is much larger than rvck(G)rvck(G) and vice versa so that we cannot in general bound one of rck(G)rck(G) and rvck(G)rvck(G) in terms of the other.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,