TY - JOUR

T1 - Total rainbow k-connection in graphs

AU - Sousa, Teresa Maria Jerónimo

AU - Liu, Henry Chung Hang

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Let k be a positive integer and G be a k-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow k-connection number rck(G) of G. An edge-coloured path is rainbow if its edges have distinct colours. Then, rck(G) is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rck(G) has since been studied by numerous researchers. An analogue of the function rck(G) involving vertex colourings, the rainbow vertex k-connection number rvck(G), was subsequently introduced. In this paper, we introduce a version which involves total colourings. A total-coloured path is total-rainbow if its edges and internal vertices have distinct colours. The total rainbow k-connection number of G, denoted by trck(G), is the minimum number of colours required to colour the edges and vertices of G, so that any two vertices of G are connected by k internally vertex-disjoint total-rainbow paths. We study the function trck(G) when G is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rck(G), rvck(G), and trck(G), by considering how close and how far apart trck(G) can be from rck(G) and rvck(G).

AB - Let k be a positive integer and G be a k-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow k-connection number rck(G) of G. An edge-coloured path is rainbow if its edges have distinct colours. Then, rck(G) is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rck(G) has since been studied by numerous researchers. An analogue of the function rck(G) involving vertex colourings, the rainbow vertex k-connection number rvck(G), was subsequently introduced. In this paper, we introduce a version which involves total colourings. A total-coloured path is total-rainbow if its edges and internal vertices have distinct colours. The total rainbow k-connection number of G, denoted by trck(G), is the minimum number of colours required to colour the edges and vertices of G, so that any two vertices of G are connected by k internally vertex-disjoint total-rainbow paths. We study the function trck(G) when G is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rck(G), rvck(G), and trck(G), by considering how close and how far apart trck(G) can be from rck(G) and rvck(G).

KW - Graph colouring

KW - k-connected

KW - rainbow (vertex) connection number

U2 - 10.1016/j.dam.2014.04.012

DO - 10.1016/j.dam.2014.04.012

M3 - Article

VL - 174

SP - 92

EP - 101

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - NA

ER -