Rainbow vertex k-connection in graphs

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

Let k be a positive integer and G be a k-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow k-connection number of G, denoted by rck(G), isthe minimum number of colours required to colour the edges of G so that any two verticesof G are connected by k internally vertex-disjoint rainbow paths. The function rck(G) wasfirst 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) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex k-connection number of G, denoted by rvck(G),is the minimum number of colours required to colour the vertices of G so that any two vertices of G are connected by k internally vertex-disjoint vertex-rainbow paths. We shall study the function rvck(G) when G is a cycle, a wheel, and a complete multipartite graph. We also construct graphs G where rck(G) is much larger than rvck(G) and vice versa so that we cannot in general bound one of rck(G) and rvck(G) in terms of the other.
Original languageUnknown
Pages (from-to)2549-2555
JournalDiscrete Applied Mathematics
Volume161
Issue number16-17
DOIs
Publication statusPublished - 1 Jan 2013

Cite this