Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421162 | Discrete Applied Mathematics | 2014 | 10 Pages |
Let kk be a positive integer and GG be a kk-connected graph. In 2009, Chartrand, Johns, McKeon, and Zhang introduced the rainbow kk-connection number rck(G)rck(G) of GG. An edge-coloured path is rainbow if its edges have distinct colours. Then, 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) has since been studied by numerous researchers. An analogue of the function rck(G)rck(G) involving vertex colourings, the rainbow vertex kk-connection number rvck(G)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 kk-connection number of GG, denoted by trck(G)trck(G), is the minimum number of colours required to colour the edges and vertices of GG, so that any two vertices of GG are connected by kk internally vertex-disjoint total-rainbow paths. We study the function trck(G)trck(G) when GG is a cycle, a wheel, and a complete multipartite graph. We also compare the functions rck(G)rck(G), rvck(G)rvck(G), and trck(G)trck(G), by considering how close and how far apart trck(G)trck(G) can be from rck(G)rck(G) and rvck(G)rvck(G).