TY - JOUR

T1 - Rainbow vertex k-connection in graphs

AU - Sousa, Teresa Maria Jerónimo

AU - Liu, Henry Chung Hang

PY - 2013/1/1

Y1 - 2013/1/1

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

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

KW - Graph colouring

KW - k-connected

KW - rainbow (vertex) connection number

U2 - 10.1016/j.dam.2013.04.025

DO - 10.1016/j.dam.2013.04.025

M3 - Article

VL - 161

SP - 2549

EP - 2555

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 16-17

ER -